
<!DOCTYPE HTML>
<html lang="" >
    <head>
        <meta charset="UTF-8">
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <title>六、C++STL C库函数 · CppInterview</title>
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="description" content="">
        <meta name="generator" content="GitBook 3.2.3">
        <meta name="author" content="songzhuozhu">
        
        
    
    <link rel="stylesheet" href="../gitbook/style.css">

    
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-intopic-toc/style.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-back-to-top-button/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-search-pro/search.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-splitter/splitter.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-pageview-count/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-highlight/website.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-fontsettings/website.css">
                
            
        

    

    
        
    
        
    
        
    
        
    
        
    
        
    

        
    
    
    <meta name="HandheldFriendly" content="true"/>
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
    <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">

    
    <link rel="next" href="../七、C++新特性/" />
    
    
    <link rel="prev" href="../五、C++内存管理/" />
    

    </head>
    <body>
        
<div class="book">
    <div class="book-summary">
        
            
<div id="book-search-input" role="search">
    <input type="text" placeholder="Type to search" />
</div>

            
                <nav role="navigation">
                


<ul class="summary">
    
    

    

    
        
        
    
        <li class="chapter " data-level="1.1" data-path="../">
            
                <a href="../">
            
                    
                    简介
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="../一、C++基础知识/">
            
                <a href="../一、C++基础知识/">
            
                    
                    一、C++基础知识
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="../二、C++指针与引用/">
            
                <a href="../二、C++指针与引用/">
            
                    
                    二、C++指针与引用
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4" data-path="../三、C++关键字/">
            
                <a href="../三、C++关键字/">
            
                    
                    三、C++关键字
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5" data-path="../四、C++面向对象/">
            
                <a href="../四、C++面向对象/">
            
                    
                    四、C++面向对象
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.6" data-path="../五、C++内存管理/">
            
                <a href="../五、C++内存管理/">
            
                    
                    五、C++内存管理
            
                </a>
            

            
        </li>
    
        <li class="chapter active" data-level="1.7" data-path="./">
            
                <a href="./">
            
                    
                    六、C++STL C库函数
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.8" data-path="../七、C++新特性/">
            
                <a href="../七、C++新特性/">
            
                    
                    七、C++新特性
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.9" data-path="../八、计算机网络/">
            
                <a href="../八、计算机网络/">
            
                    
                    八、计算机网络
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.10" data-path="../九、网络编程/">
            
                <a href="../九、网络编程/">
            
                    
                    九、网络编程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.11" data-path="../十、操作系统/">
            
                <a href="../十、操作系统/">
            
                    
                    十、操作系统
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.12" data-path="../十一、Linux/">
            
                <a href="../十一、Linux/">
            
                    
                    十一、Linux
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.13" data-path="../十二、数据库/">
            
                <a href="../十二、数据库/">
            
                    
                    十二、数据库
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.14" data-path="../十三、软件测试/">
            
                <a href="../十三、软件测试/">
            
                    
                    十三、软件测试
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.15" data-path="../十四、面试高频手写算法/">
            
                <a href="../十四、面试高频手写算法/">
            
                    
                    十四、面试高频手写算法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.16" data-path="../十五、补充题目/">
            
                <a href="../十五、补充题目/">
            
                    
                    十五、补充题目
            
                </a>
            

            
        </li>
    

    

    <li class="divider"></li>

    <li>
        <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
            Published with GitBook
        </a>
    </li>
</ul>


                </nav>
            
        
    </div>

    <div class="book-body">
        
            <div class="body-inner">
                
                    

<div class="book-header" role="navigation">
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href=".." >六、C++STL C库函数</a>
    </h1>
</div>




                    <div class="page-wrapper" tabindex="-1" role="main">
                        <div class="page-inner">
                            
<div id="book-search-results">
    <div class="search-noresults">
    
                                <section class="normal markdown-section">
                                
                                <h2 id="&#x516D;&#x3001;stl--c&#x5E93;&#x51FD;&#x6570;&#xFF1A;">&#x516D;&#x3001;STL &amp; C&#x5E93;&#x51FD;&#x6570;&#xFF1A;</h2>
<h3 id="1---&#x4EC0;&#x4E48;&#x662F;stl&#xFF1F;stl&#x6709;&#x54EA;&#x4E9B;&#x5BB9;&#x5668;&#xFF1F;&#x5206;&#x522B;&#x6709;&#x4EC0;&#x4E48;&#x7279;&#x70B9;&#xFF1F;">1 - &#x4EC0;&#x4E48;&#x662F;STL&#xFF1F;STL&#x6709;&#x54EA;&#x4E9B;&#x5BB9;&#x5668;&#xFF1F;&#x5206;&#x522B;&#x6709;&#x4EC0;&#x4E48;&#x7279;&#x70B9;&#xFF1F;</h3>
<h4 id="11-stl&#x7EC4;&#x6210;">1.1 STL&#x7EC4;&#x6210;</h4>
<h5 id="&#x7B80;&#x5355;&#x6982;&#x62EC;&#xFF1A;">&#x7B80;&#x5355;&#x6982;&#x62EC;&#xFF1A;</h5>
<p><strong>C++STL&#x4ECE;&#x5E7F;&#x4E49;&#x4E0A;&#x6765;&#x8BB2;&#x5305;&#x62EC;&#x4E86;&#x4E09;&#x7C7B;&#xFF1A;&#x7B97;&#x6CD5;&#xFF0C;&#x5BB9;&#x5668;&#x548C;&#x8FED;&#x4EE3;&#x5668;</strong></p>
<ul>
<li>&#x7B97;&#x6CD5;&#x5305;&#x62EC;&#x6392;&#x5E8F;&#xFF0C;&#x62F7;&#x8D1D;&#x7B49;&#x5E38;&#x7528;&#x7B97;&#x6CD5;&#xFF0C;&#x4EE5;&#x53CA;&#x4E0D;&#x540C;&#x5BB9;&#x5668;&#x7279;&#x5B9A;&#x7684;&#x7B97;&#x6CD5;</li>
<li>&#x5BB9;&#x5668;&#x5C31;&#x662F;&#x6570;&#x636E;&#x7684;&#x5B58;&#x653E;&#x5F62;&#x5F0F;&#xFF0C;&#x5305;&#x62EC;&#x5E8F;&#x5217;&#x5BB9;&#x5668;&#x548C;&#x5173;&#x8054;&#x5F0F;&#x5BB9;&#x5668;<ul>
<li>&#x5E8F;&#x5217;&#x5BB9;&#x5668;&#xFF1A;list&#x3001;vector&#x7B49;</li>
<li>&#x5173;&#x8054;&#x5BB9;&#x5668;&#xFF1A;set&#x3001;map&#x7B49;</li>
</ul>
</li>
<li>&#x8FED;&#x4EE3;&#x5668;&#x5C31;&#x662F;&#x5728;&#x4E0D;&#x66B4;&#x9732;&#x5BB9;&#x5668;&#x5185;&#x90E8;&#x7ED3;&#x6784;&#x7684;&#x60C5;&#x51B5;&#x4E0B;&#x5BF9;&#x5BB9;&#x5668;&#x7684;&#x904D;&#x5386;</li>
</ul>
<h5 id="&#x8BE6;&#x7EC6;&#x8BF4;&#x660E;&#xFF1A;">&#x8BE6;&#x7EC6;&#x8BF4;&#x660E;&#xFF1A;</h5>
<ul>
<li><strong>&#x5BB9;&#x5668;&#xFF1A;</strong>&#x4E00;&#x4E9B;&#x5C01;&#x88C5;&#x6570;&#x636E;&#x7ED3;&#x6784;&#x7684;&#x6A21;&#x677F;&#x7C7B;&#xFF0C;&#x4F8B;&#x5982; vector &#x5411;&#x91CF;&#x5BB9;&#x5668;&#x3001;list &#x5217;&#x8868;&#x5BB9;&#x5668;&#x7B49;&#x3002;</li>
<li><strong>&#x7B97;&#x6CD5;&#xFF1A;</strong>STL &#x63D0;&#x4F9B;&#x4E86;&#x975E;&#x5E38;&#x591A;&#xFF08;&#x5927;&#x7EA6; 100 &#x4E2A;&#xFF09;&#x7684;&#x6570;&#x636E;&#x7ED3;&#x6784;&#x7B97;&#x6CD5;&#xFF0C;&#x5B83;&#x4EEC;&#x90FD;&#x88AB;&#x8BBE;&#x8BA1;&#x6210;&#x4E00;&#x4E2A;&#x4E2A;&#x7684;&#x6A21;&#x677F;&#x51FD;&#x6570;&#xFF0C;&#x8FD9;&#x4E9B;&#x7B97;&#x6CD5;&#x5728; std &#x547D;&#x540D;&#x7A7A;&#x95F4;&#x4E2D;&#x5B9A;&#x4E49;&#xFF0C;&#x5176;&#x4E2D;&#x5927;&#x90E8;&#x5206;&#x7B97;&#x6CD5;&#x90FD;&#x5305;&#x542B;&#x5728;&#x5934;&#x6587;&#x4EF6;<code>&lt;algorithm&gt;</code> &#x4E2D;&#xFF0C;&#x5C11;&#x90E8;&#x5206;&#x4F4D;&#x4E8E;&#x5934;&#x6587;&#x4EF6; <code>&lt;numeric&gt;</code> &#x4E2D;&#x3002;</li>
<li><strong>&#x8FED;&#x4EE3;&#x5668;&#xFF1A;</strong>&#x5728;C++STL &#x4E2D;&#xFF0C;&#x5BF9;&#x5BB9;&#x5668;&#x4E2D;&#x6570;&#x636E;&#x7684;&#x8BFB;&#x548C;&#x5199;&#xFF0C;&#x662F;&#x901A;&#x8FC7;&#x8FED;&#x4EE3;&#x5668;&#x5B8C;&#x6210;&#x7684;&#xFF0C;&#x626E;&#x6F14;&#x7740;&#x5BB9;&#x5668;&#x548C;&#x7B97;&#x6CD5;&#x4E4B;&#x95F4;&#x7684;&#x80F6;&#x5408;&#x5242;&#x3002;</li>
<li><strong>&#x51FD;&#x6570;&#x5BF9;&#x8C61;&#xFF1A;</strong>&#x5982;&#x679C;&#x4E00;&#x4E2A;&#x7C7B;&#x5C06; () &#x8FD0;&#x7B97;&#x7B26;&#x91CD;&#x8F7D;&#x4E3A;&#x6210;&#x5458;&#x51FD;&#x6570;&#xFF0C;&#x8FD9;&#x4E2A;&#x7C7B;&#x5C31;&#x79F0;&#x4E3A;&#x51FD;&#x6570;&#x5BF9;&#x8C61;&#x7C7B;&#xFF0C;&#x8FD9;&#x4E2A;&#x7C7B;&#x7684;&#x5BF9;&#x8C61;&#x5C31;&#x662F;&#x51FD;&#x6570;&#x5BF9;&#x8C61;&#xFF08;&#x53C8;&#x79F0;&#x4EFF;&#x51FD;&#x6570;&#xFF09;&#x3002;</li>
<li><strong>&#x9002;&#x914D;&#x5668;&#xFF1A;</strong>&#x53EF;&#x4EE5;&#x4F7F;&#x4E00;&#x4E2A;&#x7C7B;&#x7684;&#x63A5;&#x53E3;&#xFF08;&#x6A21;&#x677F;&#x7684;&#x53C2;&#x6570;&#xFF09;&#x9002;&#x914D;&#x6210;&#x7528;&#x6237;&#x6307;&#x5B9A;&#x7684;&#x5F62;&#x5F0F;&#xFF0C;&#x4ECE;&#x800C;&#x8BA9;&#x539F;&#x672C;&#x4E0D;&#x80FD;&#x5728;&#x4E00;&#x8D77;&#x5DE5;&#x4F5C;&#x7684;&#x4E24;&#x4E2A;&#x7C7B;&#x5DE5;&#x4F5C;&#x5728;&#x4E00;&#x8D77;&#x3002;&#x503C;&#x5F97;&#x4E00;&#x63D0;&#x7684;&#x662F;&#xFF0C;&#x5BB9;&#x5668;&#x3001;&#x8FED;&#x4EE3;&#x5668;&#x548C;&#x51FD;&#x6570;&#x90FD;&#x6709;&#x9002;&#x914D;&#x5668;&#x3002;</li>
<li><strong>&#x5185;&#x5B58;&#x5206;&#x914D;&#x5668;&#xFF1A;</strong>&#x4E3A;&#x5BB9;&#x5668;&#x7C7B;&#x6A21;&#x677F;&#x63D0;&#x4F9B;&#x81EA;&#x5B9A;&#x4E49;&#x7684;&#x5185;&#x5B58;&#x7533;&#x8BF7;&#x548C;&#x91CA;&#x653E;&#x529F;&#x80FD;&#xFF0C;&#x7531;&#x4E8E;&#x5F80;&#x5F80;&#x53EA;&#x6709;&#x9AD8;&#x7EA7;&#x7528;&#x6237;&#x624D;&#x6709;&#x6539;&#x53D8;&#x5185;&#x5B58;&#x5206;&#x914D;&#x7B56;&#x7565;&#x7684;&#x9700;&#x6C42;&#xFF0C;&#x56E0;&#x6B64;&#x5185;&#x5B58;&#x5206;&#x914D;&#x5668;&#x5BF9;&#x4E8E;&#x4E00;&#x822C;&#x7528;&#x6237;&#x6765;&#x8BF4;&#xFF0C;&#x5E76;&#x4E0D;&#x5E38;&#x7528;&#x3002;</li>
</ul>
<p>&#x5176;&#x4E2D;<strong>&#x8FED;&#x4EE3;&#x5668;&#x3001;&#x51FD;&#x6570;&#x5BF9;&#x8C61;&#x3001;&#x9002;&#x914D;&#x5668;&#x3001;&#x5185;&#x5B58;&#x5206;&#x914D;&#x5668;</strong>&#x8FD9;&#x56DB;&#x90E8;&#x5206;&#x662F;&#x4E3A;<strong>&#x5BB9;&#x5668;&#x548C;&#x7B97;&#x6CD5;</strong>&#x670D;&#x52A1;&#x7684;&#xFF1A;</p>
<ul>
<li>&#x7B97;&#x6CD5;&#x901A;&#x8FC7;<strong>&#x8FED;&#x4EE3;&#x5668;</strong>&#x83B7;&#x53D6;&#x5BB9;&#x5668;&#x4E2D;&#x7684;&#x5185;&#x5BB9;</li>
<li><strong>&#x51FD;&#x6570;&#x5BF9;&#x8C61;</strong>&#x53EF;&#x4EE5;&#x534F;&#x52A9;&#x7B97;&#x6CD5;&#x5B8C;&#x6210;&#x5404;&#x79CD;&#x64CD;&#x4F5C;</li>
<li><strong>&#x9002;&#x914D;&#x5668;</strong>&#x7528;&#x6765;&#x5957;&#x63A5;&#x9002;&#x914D;&#x4EFF;&#x51FD;&#x6570;</li>
<li><strong>&#x5185;&#x5B58;&#x5206;&#x914D;&#x5668;</strong>&#x7ED9;&#x5BB9;&#x5668;&#x5206;&#x914D;&#x5B58;&#x50A8;&#x7A7A;&#x95F4;</li>
</ul>
<p>&#x5728;&#x60E0;&#x666E;&#x5B9E;&#x9A8C;&#x5BA4;&#x6700;&#x521D;&#x53D1;&#x884C;&#x7684;&#x7248;&#x672C;&#x4E2D;&#xFF0C;STL &#x88AB;&#x7EC4;&#x7EC7;&#x6210; 48 &#x4E2A;&#x5934;&#x6587;&#x4EF6;&#xFF1B;&#x4F46;&#x5728; C++ &#x6807;&#x51C6;&#x4E2D;&#xFF0C;&#x5B83;&#x4EEC;&#x88AB;&#x91CD;&#x65B0;&#x7EC4;&#x7EC7;&#x4E3A; 13 &#x4E2A;&#x5934;&#x6587;&#x4EF6;&#xFF1A;</p>
<table>
<thead>
<tr>
<th><code>&lt;iterator&gt;</code></th>
<th><code>&lt;functional&gt;</code></th>
<th><code>&lt;vector&gt;</code></th>
<th><code>&lt;deque&gt;</code></th>
</tr>
</thead>
<tbody>
<tr>
<td><code>&lt;list&gt;</code></td>
<td><code>&lt;queue&gt;</code></td>
<td><code>&lt;stack&gt;</code></td>
<td><code>&lt;set&gt;</code></td>
</tr>
<tr>
<td><code>&lt;map&gt;</code></td>
<td><code>&lt;algorithm&gt;</code></td>
<td><code>&lt;numeric&gt;</code></td>
<td><code>&lt;memory&gt;</code></td>
</tr>
<tr>
<td><code>&lt;utility&gt;</code></td>
<td></td>
<td></td>
</tr>
</tbody>
</table>
<h4 id="12-stl&#x5BB9;&#x5668;&#x5206;&#x7C7B;">1.2 STL&#x5BB9;&#x5668;&#x5206;&#x7C7B;</h4>
<p>&#x6807;&#x51C6;&#x5E93;&#x7684;&#x5BB9;&#x5668;&#x5206;&#x4E3A;&#x4E09;&#x7C7B;&#xFF1A;&#x987A;&#x5E8F;&#x5BB9;&#x5668;&#x3001;&#x5173;&#x8054;&#x5BB9;&#x5668;&#x3001;&#x5BB9;&#x5668;&#x9002;&#x914D;&#x5668;</p>
<ul>
<li>&#x987A;&#x5E8F;&#x5BB9;&#x5668;&#x6709;&#x4E94;&#x79CD;<ul>
<li><code>array&lt;T, N&gt;</code> &#x6570;&#x7EC4;&#xFF1A;&#x56FA;&#x5B9A;&#x5927;&#x5C0F;&#x6570;&#x7EC4;&#xFF0C;&#x652F;&#x6301;&#x5FEB;&#x901F;&#x968F;&#x673A;&#x8BBF;&#x95EE;&#xFF0C;&#x4F46;&#x4E0D;&#x80FD;&#x63D2;&#x5165;&#x6216;&#x5220;&#x9664;&#x5143;&#x7D20;</li>
<li><code>vector&lt;T&gt;</code> &#x52A8;&#x6001;&#x6570;&#x7EC4;&#xFF1A;&#x652F;&#x6301;&#x5FEB;&#x901F;&#x968F;&#x673A;&#x8BBF;&#x95EE;&#xFF0C;&#x5C3E;&#x90E8;&#x63D2;&#x5165;&#x548C;&#x5220;&#x9664;&#x7684;&#x901F;&#x5EA6;&#x5FEB;</li>
<li><code>deque&lt;T&gt;</code> &#x53CC;&#x5411;&#x961F;&#x5217;&#xFF1A;&#x652F;&#x6301;&#x5FEB;&#x901F;&#x968F;&#x673A;&#x8BBF;&#x95EE;&#xFF0C;&#x9996;&#x5C3E;&#x4F4D;&#x7F6E;&#x63D2;&#x5165;&#x548C;&#x5220;&#x9664;&#x901F;&#x5EA6;&#x5FEB;</li>
<li><code>list&lt;T&gt;</code>&#x53CC;&#x5411;&#x94FE;&#x8868;&#xFF1A;&#x53EA;&#x652F;&#x6301;&#x53CC;&#x5411;&#x987A;&#x5E8F;&#x8BBF;&#x95EE;&#xFF0C;&#x4EFB;&#x4F55;&#x4F4D;&#x7F6E;&#x63D2;&#x5165;&#x548C;&#x5220;&#x9664;&#x901F;&#x5EA6;&#x90FD;&#x5F88;&#x5FEB;</li>
<li><code>forward_list&lt;T&gt;</code> &#x5355;&#x5411;&#x94FE;&#x8868;&#xFF1A;&#x53EA;&#x652F;&#x6301;&#x5355;&#x5411;&#x987A;&#x5E8F;&#x8BBF;&#x95EE;&#xFF0C;&#x4EFB;&#x4F55;&#x4F4D;&#x7F6E;&#x63D2;&#x5165;&#x548C;&#x5220;&#x9664;&#x7684;&#x901F;&#x5EA6;&#x90FD;&#x5F88;&#x5FEB;</li>
</ul>
</li>
<li>&#x5173;&#x8054;&#x5BB9;&#x5668;&#x6709;&#x4E24;&#x79CD;<ul>
<li>map&#x5BB9;&#x5668;&#xFF1A;<ul>
<li><code>map&lt;K, T&gt;</code> </li>
<li><code>multimap&lt;K, T&gt;</code> </li>
<li><code>unordered_map&lt;K, T&gt;</code></li>
<li><code>unordered_multimap&lt;K, T&gt;</code></li>
</ul>
</li>
<li>set&#x5BB9;&#x5668;&#xFF1A;<ul>
<li><code>set&lt;T&gt;</code></li>
<li><code>multiset&lt;T&gt;</code></li>
<li><code>unordered_set&lt;T&gt;</code></li>
<li><code>unordered_multiset&lt;T&gt;</code></li>
</ul>
</li>
</ul>
</li>
<li>&#x5BB9;&#x5668;&#x9002;&#x914D;&#x5668;&#x6709;&#x4E09;&#x79CD;&#xFF1A;<ul>
<li><code>stack&lt;T&gt;</code></li>
<li><code>queue&lt;T&gt;</code></li>
<li><code>priority_queue&lt;T&gt;</code></li>
</ul>
</li>
</ul>
<h3 id="2---&#x4EC0;&#x4E48;&#x65F6;&#x5019;&#x7528;hashmap&#xFF0C;&#x4EC0;&#x4E48;&#x65F6;&#x5019;&#x7528;map&#xFF1F;">2 - &#x4EC0;&#x4E48;&#x65F6;&#x5019;&#x7528;hash_map&#xFF0C;&#x4EC0;&#x4E48;&#x65F6;&#x5019;&#x7528;map&#xFF1F;</h3>
<ul>
<li>hash_map&#x67E5;&#x627E;&#x901F;&#x5EA6;&#x6BD4;map&#x5FEB;&#xFF0C;&#x67E5;&#x627E;&#x901F;&#x5EA6;&#x5C5E;&#x4E8E;&#x5E38;&#x6570;&#x7EA7;&#x522B;&#xFF1B;map&#x7684;&#x67E5;&#x627E;&#x901F;&#x5EA6;&#x662F; $\log{n}$ &#x7EA7;&#x522B;</li>
<li><strong>&#x5220;&#x9664;&#x548C;&#x63D2;&#x5165;&#x64CD;&#x4F5C;&#x8F83;&#x591A;&#x7684;&#x60C5;&#x51B5;&#x4E0B;&#xFF0C;map&#x6BD4;hash_map&#x7684;&#x6027;&#x80FD;&#x66F4;&#x597D;&#xFF0C;&#x6570;&#x636E;&#x91CF;&#x8D8A;&#x5927;&#x8D8A;&#x660E;&#x663E;</strong></li>
<li>map&#x7684;&#x904D;&#x5386;&#x6027;&#x80FD;&#x9AD8;&#x4E8E;hash_map&#xFF0C;</li>
<li>hash_map &#x67E5;&#x627E;&#x6027;&#x80FD; &#x6BD4;map&#x8981;&#x597D;&#xFF0C;&#x6570;&#x636E;&#x91CF;&#x8D8A;&#x5927;&#xFF0C;&#x67E5;&#x627E;&#x6B21;&#x6570;&#x8D8A;&#x591A;&#xFF0C;hash_map&#x8868;&#x73B0;&#x5C31;&#x8D8A;&#x597D;&#x3002;</li>
</ul>
<p>&#x4F46;&#x662F;&#x5E76;&#x4E0D;&#x4E00;&#x5B9A;&#x5E38;&#x6570;&#x5C31;&#x6BD4;$\log{n}$ &#x5C0F;&#xFF0C;hash&#x8FD8;&#x6709;hash&#x51FD;&#x6570;&#x7684;&#x8017;&#x65F6;&#x3002;&#x5F53;&#x5143;&#x7D20;&#x8FBE;&#x5230;&#x4E00;&#x5B9A;&#x7684;&#x6570;&#x91CF;&#x7EA7;&#x65F6;&#xFF0C;&#x4F18;&#x5148;&#x8003;&#x8651;hash_map&#xFF1B;&#x82E5;&#x5BF9;&#x5185;&#x5B58;&#x4F7F;&#x7528;&#x91CF;&#x6709;&#x4E25;&#x683C;&#x8981;&#x6C42;&#xFF0C;hash_map&#x9700;&#x8981;&#x614E;&#x9009;&#xFF0C;&#x800C;&#x4E14;hash_map&#x6784;&#x9020;&#x901F;&#x5EA6;&#x8F83;&#x6162;&#x3002;&#x6240;&#x4EE5;&#x5982;&#x4F55;&#x9009;&#x62E9;&#xFF0C;&#x4E3B;&#x8981;&#x6743;&#x8861;&#x4E09;&#x4E2A;&#x56E0;&#x7D20;&#xFF1A;&#x67E5;&#x627E;&#x901F;&#x5EA6;&#x3001;&#x6570;&#x636E;&#x91CF;&#x3001;&#x5185;&#x5B58;&#x4F7F;&#x7528;</p>
<h3 id="3---stl&#x4E2D;&#x54C8;&#x5E0C;&#x8868;&#x7684;&#x5E95;&#x5C42;&#x5B9E;&#x73B0;">3 - STL&#x4E2D;&#x54C8;&#x5E0C;&#x8868;&#x7684;&#x5E95;&#x5C42;&#x5B9E;&#x73B0;</h3>
<p>Hashtable&#x5728;C++&#x7684;STL&#x91CC;&#x5360;&#x636E;&#x7740;&#x91CD;&#x8981;&#x7684;&#x4E00;&#x5E2D;&#x4E4B;&#x5730;&#x3002;&#x5176;&#x4E2D;&#x7684;hash_set&#x3001;hash_map&#x3001;hash_multiset&#x3001;hash_multimap&#x56DB;&#x4E2A;&#x5173;&#x8054;&#x5BB9;&#x5668;&#x90FD;&#x662F;&#x4EE5;hashtable&#x4E3A;&#x5E95;&#x5C42;&#x5B9E;&#x73B0;&#x65B9;&#x6CD5;&#xFF08;&#x6280;&#x5DE7;&#xFF09;</p>
<ul>
<li><p>Hashtable&#x5E95;&#x5C42;&#x5B9E;&#x73B0;&#x662F;&#x901A;&#x8FC7;<strong>&#x5F00;&#x94FE;&#x6CD5;</strong>&#x6765;&#x5B9E;&#x73B0;&#x7684;&#xFF0C;hash table&#x8868;&#x683C;&#x5185;&#x7684;&#x5143;&#x7D20;&#x79F0;&#x4E3A;&#x6876;&#xFF08;bucket)&#xFF0C;bucket&#x662F;hashtable_node&#x6570;&#x636E;&#x7ED3;&#x6784;&#x7EC4;&#x6210;&#x7684;&#x94FE;&#x8868;&#xFF0C;&#x5B9A;&#x4E49;&#x5982;&#x4E0B;&#xFF0C;&#x901A;&#x8FC7;&#x5F53;&#x524D;&#x8282;&#x70B9;&#xFF0C;&#x53EF;&#x4EE5;&#x65B9;&#x4FBF;&#x5730;&#x901A;&#x8FC7;&#x8282;&#x70B9;&#x81EA;&#x8EAB;&#x7684;next&#x6307;&#x9488;&#x6765;&#x83B7;&#x53D6;&#x4E0B;&#x4E00;&#x94FE;&#x8868;&#x8282;&#x70B9;&#x7684;&#x5143;&#x7D20;&#x3002;</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">template</span>&lt;<span class="hljs-keyword">class</span> Value&gt;
<span class="hljs-keyword">struct</span> __hashtable_node
{
    __hashtable_node *next;
    Value val;
};
</code></pre>
</li>
</ul>
<ul>
<li><p><strong>&#x5B58;&#x5165;&#x6876;&#x5143;&#x7D20;&#x7684;&#x5BB9;&#x5668;&#x662F;vector</strong>&#x3002;&#x9009;&#x62E9;vector&#x4E3A;&#x5B58;&#x653E;&#x6876;&#x5143;&#x7D20;&#xFF08;bucket&#xFF09;&#x7684;&#x57FA;&#x7840;&#x5BB9;&#x5668;&#xFF0C;&#x662F;&#x56E0;&#x4E3A;vector&#x5BB9;&#x5668;&#x672C;&#x8EAB;&#x5177;&#x6709;&#x52A8;&#x6001;&#x6269;&#x5BB9;&#x80FD;&#x529B;&#xFF0C;&#x65E0;&#x9700;&#x4EBA;&#x5DE5;&#x5E72;&#x9884;&#x3002;</p>
</li>
<li><p>&#x5728;&#x5F00;&#x94FE;&#x65B9;&#x6CD5;&#x4E2D;&#xFF0C;&#x7528;&#x4E8E;&#x88C5;&#x8F7D;&#x6876;&#x5143;&#x7D20;&#xFF08;bucket&#xFF09;&#x7684;vector&#x5BB9;&#x5668;&#x5927;&#x5C0F;&#x6052;&#x5B9A;&#x4E3A;&#x4E00;&#x4E2A;&#x8D28;&#x6570;&#x5927;&#x5C0F;&#xFF0C;&#x54C8;&#x5E0C;&#x8868;&#x5185;&#x7F6E;&#x4E86;28&#x4E2A;&#x8D28;&#x6570;&#xFF08;53,97,193&#xFF0C;...&#xFF0C;429496729&#xFF09;&#x3002;&#x5728;&#x521B;&#x5EFA;&#x54C8;&#x5E0C;&#x8868;&#x65F6;&#xFF0C;&#x4F1A;&#x6839;&#x636E;&#x5B58;&#x5165;&#x7684;&#x5143;&#x7D20;&#x4E2A;&#x6570;&#x9009;&#x62E9;&#x5927;&#x4E8E;&#x7B49;&#x4E8E;&#x5143;&#x7D20;&#x4E2A;&#x6570;&#x7684;&#x8D28;&#x6570;&#x4F5C;&#x4E3A;&#x54C8;&#x5E0C;&#x8868;&#x7684;&#x5BB9;&#x91CF;&#xFF0C;&#x5373;vector&#x7684;&#x957F;&#x5EA6;&#xFF0C;&#x5176;&#x4E2D;&#x6BCF;&#x4E2A;&#x6876;&#xFF08;bucket&#xFF09;&#x6240;&#x7EF4;&#x62A4;&#x7684;&#x94FE;&#x8868;&#x957F;&#x5EA6;&#x4E5F;&#x7B49;&#x4E8E;&#x54C8;&#x5E0C;&#x8868;&#x7684;&#x5BB9;&#x91CF;&#x3002;&#x5982;&#x679C;&#x63D2;&#x5165;&#x54C8;&#x5E0C;&#x8868;&#x7684;&#x5143;&#x7D20;&#x8D85;&#x8FC7;&#x4E86;&#x6876;&#xFF08;bucket&#xFF09;&#x7684;&#x5BB9;&#x91CF;&#xFF0C;&#x5C31;&#x8981;&#x91CD;&#x5EFA;&#x54C8;&#x5E0C;&#x8868;&#xFF0C;&#x5373;&#x627E;&#x51FA;&#x4E0B;&#x4E00;&#x4E2A;&#x8D28;&#x6570;&#xFF0C;&#x521B;&#x5EFA;&#x65B0;&#x7684;buckets &#x3001;vector&#xFF0C;&#x91CD;&#x65B0;&#x8BA1;&#x7B97;&#x5143;&#x7D20;&#x5728;&#x65B0;&#x54C8;&#x5E0C;&#x8868;&#x7684;&#x4F4D;&#x7F6E;&#xFF0C;&#x7136;&#x540E;&#x518D;delete&#x6389;old hashtable&#x7684;&#x6240;&#x6709;&#x5143;&#x7D20;&#x3002;</p>
</li>
</ul>
<p>hash_table&#x7684;&#x4E00;&#x4E9B;&#x7EC6;&#x8282;&#xFF1A;</p>
<ul>
<li>&#x5176;&#x8FED;&#x4EE3;&#x5668;&#x6CA1;&#x6709;&#x51CF;&#x64CD;&#x4F5C;&#xFF0C;&#x4E5F;&#x6CA1;&#x6709;&#x9006;&#x5411;&#x8FED;&#x4EE3;&#x5668;&#x3002;</li>
<li>&#x4E0D;&#x80FD;&#x5904;&#x7406; string double float&#x7B49;&#x7C7B;&#x578B;&#x3002;</li>
</ul>
<h3 id="4---&#x54C8;&#x5E0C;&#x6784;&#x9020;&#x51FD;&#x6570;&#x548C;&#x54C8;&#x5E0C;&#x51B2;&#x7A81;&#x7B97;&#x6CD5;&#x6709;&#x54EA;&#x4E9B;&#xFF1F;">4 - &#x54C8;&#x5E0C;&#x6784;&#x9020;&#x51FD;&#x6570;&#x548C;&#x54C8;&#x5E0C;&#x51B2;&#x7A81;&#x7B97;&#x6CD5;&#x6709;&#x54EA;&#x4E9B;&#xFF1F;</h3>
<h4 id="&#x54C8;&#x5E0C;&#x6784;&#x9020;&#x51FD;&#x6570;&#xFF08;&#x8BB0;&#x4F4F;&#x524D;&#x56DB;&#x4E2A;&#xFF09;&#xFF1A;">&#x54C8;&#x5E0C;&#x6784;&#x9020;&#x51FD;&#x6570;&#xFF08;&#x8BB0;&#x4F4F;&#x524D;&#x56DB;&#x4E2A;&#xFF09;&#xFF1A;</h4>
<ul>
<li><p>&#x9664;&#x7559;&#x4F59;&#x6570;&#x6CD5;</p>
</li>
<li><p>&#x76F4;&#x63A5;&#x5B9A;&#x5740;&#x6CD5;</p>
</li>
<li>&#x6570;&#x5B57;&#x5206;&#x6790;&#x6CD5;</li>
<li>&#x5E73;&#x65B9;&#x53D6;&#x4E2D;&#x6CD5;</li>
<li>&#x6298;&#x53E0;&#x6CD5;&#x3001;&#x57FA;&#x6570;&#x8F6C;&#x6362;&#x6CD5;&#x3001;&#x968F;&#x673A;&#x6570;&#x6CD5;&#x3001;&#x968F;&#x673A;&#x4E58;&#x6570;&#x6CD5;&#x3001;&#x5B57;&#x7B26;&#x4E32;&#x6570;&#x503C;&#x54C8;&#x5E0C;&#x6CD5;&#x3001;&#x65CB;&#x8F6C;&#x6CD5;</li>
</ul>
<h4 id="&#x54C8;&#x5E0C;&#x5904;&#x7406;&#x51B2;&#x7A81;&#x65B9;&#x6CD5;&#xFF1A;">&#x54C8;&#x5E0C;&#x5904;&#x7406;&#x51B2;&#x7A81;&#x65B9;&#x6CD5;&#xFF1A;</h4>
<ul>
<li>&#x5F00;&#x94FE;&#x6CD5;</li>
<li>&#x5F00;&#x653E;&#x5B9A;&#x5740;&#x6CD5;</li>
<li>&#x518D;&#x54C8;&#x5E0C;&#x6CD5;</li>
</ul>
<h3 id="5---vector&#x5E95;&#x5C42;&#x662F;&#x600E;&#x4E48;&#x5B9E;&#x73B0;&#x7684;&#xFF1F;vector&#x76F8;&#x5173;&#x95EE;&#x9898;">5 - vector&#x5E95;&#x5C42;&#x662F;&#x600E;&#x4E48;&#x5B9E;&#x73B0;&#x7684;&#xFF1F;vector&#x76F8;&#x5173;&#x95EE;&#x9898;</h3>
<h4 id="50---vector&#x5E95;&#x5C42;">5.0 - vector&#x5E95;&#x5C42;</h4>
<p>vector&#x5E95;&#x5C42;&#x662F;&#x4E00;&#x4E2A;&#x52A8;&#x6001;&#x6570;&#x7EC4;&#xFF0C;&#x5305;&#x542B;&#x4E09;&#x4E2A;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;start &#x548C; finish &#x4E4B;&#x95F4;&#x662F;&#x5DF2;&#x7ECF;&#x88AB;&#x4F7F;&#x7528;&#x7684;&#x7A7A;&#x95F4;&#x8303;&#x56F4;&#xFF0C;end_of_storage&#x662F;&#x6574;&#x5757;&#x8FDE;&#x7EED;&#x7A7A;&#x95F4;&#x5305;&#x62EC;&#x5907;&#x7528;&#x7A7A;&#x95F4;&#x7684;&#x5C3E;&#x90E8;&#x3002;</p>
<p>&#x5F53;&#x7A7A;&#x95F4;&#x4E0D;&#x591F;&#x88C5;&#x4E0B;&#x6570;&#x636E;&#xFF08;v.push_back(val)&#xFF09;&#x65F6;&#xFF0C;&#x4F1A;&#x81EA;&#x52A8;&#x7533;&#x8BF7;&#x53E6;&#x4E00;&#x7247;&#x66F4;&#x5927;&#x7684;&#x7A7A;&#x95F4;&#xFF08;1.5&#x6216;2&#x500D;&#xFF09;&#xFF0C;&#x7136;&#x540E;&#x628A;&#x539F;&#x6765;&#x7684;&#x6570;&#x636E;&#x62F7;&#x8D1D;&#x5230;&#x65B0;&#x7684;&#x5185;&#x5B58;&#x7A7A;&#x95F4;&#xFF0C;&#x7136;&#x540E;&#x91CA;&#x653E;&#x539F;&#x6765;&#x7684;&#x7A7A;&#x95F4;</p>
<p>&#x5F53;&#x91CA;&#x653E;&#x6216;&#x5220;&#x9664;&#xFF08;v.clear()&#xFF09;vector&#x4E2D;&#x7684;&#x6570;&#x636E;&#x65F6;&#xFF0C;&#x5176;&#x5B58;&#x50A8;&#x7A7A;&#x95F4;&#x4E0D;&#x91CA;&#x653E;&#xFF0C;&#x53EA;&#x662F;&#x6E05;&#x7A7A;&#x4E86;&#x91CC;&#x9762;&#x7684;&#x6570;&#x636E;</p>
<p>&#x5BF9;vector&#x7684;&#x4EFB;&#x4F55;&#x64CD;&#x4F5C;&#x4E00;&#x65E6;&#x5F15;&#x8D77;&#x4E86;&#x7A7A;&#x95F4;&#x7684;&#x91CD;&#x65B0;&#x5206;&#x914D;&#xFF0C;&#x6307;&#x5411;&#x6E90;vector&#x7684;&#x6240;&#x6709;&#x8FED;&#x4EE3;&#x5668;&#x90FD;&#x4F1A;&#x5931;&#x6548;</p>
<p><img src="https://gitee.com/song-zhuozhu/my_image/raw/master/img/image-20210910184701486.png" alt="image-20210910184701486" style="zoom:67%;"></p>
<h4 id="51---vector&#x4E2D;&#x7684;-size-&#x548C;-capacity-&#x7684;&#x533A;&#x522B;">5.1 - vector&#x4E2D;&#x7684; size &#x548C; capacity &#x7684;&#x533A;&#x522B;</h4>
<ul>
<li>size &#x8868;&#x793A;&#x5F53;&#x524D;vector&#x6709;&#x591A;&#x5C11;&#x4E2A;&#x5143;&#x7D20;&#xFF08;finish - start&#xFF09;&#xFF0C;&#x800C;capacity&#x51FD;&#x6570;&#x5219;&#x8868;&#x793A;&#x5B83;&#x5DF2;&#x7ECF;&#x5206;&#x914D;&#x7684;&#x5185;&#x5B58;&#x4E2D;&#x53EF;&#x4EE5;&#x5BB9;&#x7EB3;&#x591A;&#x5C11;&#x5143;&#x7D20;&#xFF08;end_of_storage - start&#xFF09;</li>
</ul>
<h4 id="52---vector-&#x4E2D;&#x7684;-reserve--&#x548C;-resize-&#x7684;&#x533A;&#x522B;&#xFF1F;">5.2 - vector &#x4E2D;&#x7684; reserve  &#x548C; resize &#x7684;&#x533A;&#x522B;&#xFF1F;</h4>
<ul>
<li>reserve&#x662F;&#x76F4;&#x63A5;&#x6269;&#x5145;&#x5230;&#x5DF2;&#x7ECF;&#x786E;&#x5B9A;&#x7684;&#x5927;&#x5C0F;&#xFF08;newSize = capacity&#xFF09;&#xFF0C;&#x53EF;&#x4EE5;&#x51CF;&#x5C11;&#x591A;&#x6B21;&#x5F00;&#x8F9F;&#x3001;&#x91CA;&#x653E;&#x7A7A;&#x95F4;&#x7684;&#x95EE;&#x9898;&#xFF08;&#x4F18;&#x5316;push_back&#xFF09;&#x3002;&#x5C31;&#x53EF;&#x4EE5;&#x63D0;&#x9AD8;&#x6548;&#x7387;&#xFF0C;&#x5176;&#x6B21;&#x8FD8;&#x53EF;&#x4EE5;&#x51CF;&#x5C11;&#x591A;&#x6B21;&#x62F7;&#x8D1D;&#x6570;&#x636E;&#x7684;&#x95EE;&#x9898;&#x3002;reserve&#x53EA;&#x662F;&#x4FDD;&#x8BC1;vector&#x4E2D;&#x7684;&#x7A7A;&#x95F4;&#x5927;&#x5C0F;&#xFF08;capacity&#xFF0C;end_of_storage - start&#xFF09;&#x6700;&#x5C11;&#x8FBE;&#x5230;&#x53C2;&#x6570;&#x6240;&#x6307;&#x5B9A;&#x7684;&#x5927;&#x5C0F;n&#x3002;<ul>
<li>reserve (int n)</li>
</ul>
</li>
<li>resize( ) &#x53EF;&#x4EE5;&#x6539;&#x53D8;&#x6709;&#x6548;&#x7A7A;&#x95F4;&#x7684;&#x5927;&#x5C0F;(newSize = newCapacity)&#xFF0C;&#x4E5F;&#x80FD;&#x6539;&#x53D8;&#x9ED8;&#x8BA4;&#x503C;&#x7684;&#x529F;&#x80FD;&#x3002;capacity&#x7684;&#x5927;&#x5C0F;&#x4E5F;&#x4F1A;&#x968F;&#x7740;&#x6539;&#x53D8;&#x3002;<ul>
<li>resize&#xFF08;int n&#xFF0C;element&#xFF09;&#xFF0C;&#x6269;&#x5BB9;&#x540E;&#x6BCF;&#x4E2A;&#x5143;&#x7D20;&#x7684;&#x503C;&#x4E3A;element&#xFF0C;&#x9ED8;&#x8BA4;&#x4E3A;0</li>
</ul>
</li>
</ul>
<h4 id="53---vector&#x7684;&#x5143;&#x7D20;&#x7C7B;&#x578B;&#x53EF;&#x4EE5;&#x662F;&#x5F15;&#x7528;&#x5417;&#xFF1F;vector&#x5982;&#x4F55;&#x67E5;&#x627E;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#xFF1F;">5.3 - vector&#x7684;&#x5143;&#x7D20;&#x7C7B;&#x578B;&#x53EF;&#x4EE5;&#x662F;&#x5F15;&#x7528;&#x5417;&#xFF1F;vector&#x5982;&#x4F55;&#x67E5;&#x627E;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#xFF1F;</h4>
<p>&#x4E0D;&#x80FD;&#xFF0C;&#x56E0;&#x4E3A;vector&#x7684;&#x5E95;&#x5C42;&#x5B9E;&#x73B0;&#x8981;&#x6C42;&#x8FDE;&#x7EED;&#x7684;&#x5BF9;&#x8C61;&#x6392;&#x5217;&#xFF0C;&#x5F15;&#x7528;&#x5E76;&#x975E;&#x5BF9;&#x8C61;&#xFF0C;&#x6CA1;&#x6709;&#x5B9E;&#x9645;&#x5730;&#x5740;&#xFF0C;&#x56E0;&#x6B64;vector&#x7684;&#x5143;&#x7D20;&#x7C7B;&#x578B;&#x4E0D;&#x80FD;&#x662F;&#x5F15;&#x7528;&#x3002;</p>
<pre><code class="lang-cpp">find(vec.begin(),vec.end(),<span class="hljs-number">1</span>);  <span class="hljs-comment">// &#x67E5;&#x627E;1</span>
</code></pre>
<h4 id="54---vector-&#x8FED;&#x4EE3;&#x5668;&#x5931;&#x6548;&#x7684;&#x60C5;&#x51B5;&#xFF1F;">5.4 - vector &#x8FED;&#x4EE3;&#x5668;&#x5931;&#x6548;&#x7684;&#x60C5;&#x51B5;&#xFF1F;</h4>
<ul>
<li><p>&#x5F53;&#x63D2;&#x5165;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x5230;vector&#x4E2D;&#xFF0C;&#x7531;&#x4E8E;&#x5F15;&#x8D77;&#x4E86;&#x5185;&#x5B58;&#x7684;&#x91CD;&#x65B0;&#x5206;&#x914D;&#xFF0C;&#x6240;&#x4EE5;&#x6307;&#x5411;&#x539F;&#x5185;&#x5B58;&#x7684;&#x8FED;&#x4EE3;&#x5668;&#x5168;&#x90E8;&#x5931;&#x6548;&#x3002;</p>
</li>
<li><p>&#x5F53;&#x5220;&#x9664;&#x5BB9;&#x5668;&#x4E2D;&#x7684;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x540E;&#xFF0C;&#x8BE5;&#x8FED;&#x4EE3;&#x5668;&#x6240;&#x6307;&#x5411;&#x7684;&#x5143;&#x7D20;&#x5DF2;&#x7ECF;&#x88AB;&#x5220;&#x9664;&#xFF0C;&#x90A3;&#x4E48;&#x591C;&#x9020;&#x6210;&#x8FED;&#x4EE3;&#x5668;&#x7684;&#x5931;&#x6548;&#x3002;</p>
<ul>
<li>erase&#x65B9;&#x6CD5;&#x4F1A;&#x8FD4;&#x56DE;&#x4E0B;&#x4E00;&#x4E2A;&#x6709;&#x6548;&#x7684;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x6240;&#x4EE5;&#x5F53;&#x6211;&#x4EEC;&#x8981;&#x5220;&#x9664;&#x67D0;&#x4E2A;&#x5143;&#x7D20;&#x65F6;&#xFF0C;&#x9700;&#x8981; it = vec.erase(it)</li>
</ul>
</li>
</ul>
<pre><code class="lang-cpp">it = vec.erase(it);
</code></pre>
<h4 id="55---vector&#x5982;&#x4F55;&#x6B63;&#x786E;&#x91CA;&#x653E;&#x5185;&#x5B58;&#xFF1F;">5.5 - vector&#x5982;&#x4F55;&#x6B63;&#x786E;&#x91CA;&#x653E;&#x5185;&#x5B58;&#xFF1F;</h4>
<ul>
<li>vec.clear( ) : &#x6E05;&#x7A7A;&#x5185;&#x5BB9;&#xFF0C;&#x4F46;&#x4E0D;&#x91CA;&#x653E;&#x5185;&#x5B58;</li>
<li>vector( ).swap(vec) : &#x6E05;&#x7A7A;&#x5185;&#x5BB9;&#xFF0C;&#x4E14;&#x91CA;&#x653E;&#x5185;&#x5B58;&#xFF0C;&#x5F97;&#x5230;&#x4E00;&#x4E2A;&#x5168;&#x65B0;&#x7684;vector</li>
<li>vec.shrink_to_fit ( ) : &#x8BF7;&#x6C42;&#x5BB9;&#x5668;&#x964D;&#x4F4E;&#x5176;capacity &#x548C; size &#x5339;&#x914D;</li>
<li>vec.clear( ) ; vec.shrink_to_fit ( ) : &#x6E05;&#x7A7A;&#x5185;&#x5BB9;&#xFF0C;&#x4E14;&#x91CA;&#x653E;&#x5185;&#x5B58;&#x3002;</li>
</ul>
<h4 id="56---vector&#x6269;&#x5BB9;&#x4E3A;&#x4EC0;&#x4E48;&#x8981;&#x4EE5;-15-&#x6216;-2-&#x500D;-&#x6269;&#x5BB9;&#xFF1F;">5.6 - vector&#x6269;&#x5BB9;&#x4E3A;&#x4EC0;&#x4E48;&#x8981;&#x4EE5; 1.5 &#x6216; 2 &#x500D; &#x6269;&#x5BB9;&#xFF1F;</h4>
<p>&#x4EE5;2&#x500D;&#x65B9;&#x5F0F;&#x6269;&#x5BB9;&#xFF0C;&#x5BFC;&#x81F4;&#x4E0B;&#x4E00;&#x6B21;&#x7533;&#x8BF7;&#x7684;&#x5185;&#x5B58;&#x5FC5;&#x7136;&#x5927;&#x4E8E;&#x4E4B;&#x524D;&#x5206;&#x914D;&#x7684;&#x5185;&#x5B58;&#x603B;&#x548C;&#xFF0C;&#x5BFC;&#x81F4;&#x4E4B;&#x524D;&#x5206;&#x914D;&#x7684;&#x5185;&#x5B58;&#x4E0D;&#x80FD;&#x518D;&#x88AB;&#x4F7F;&#x7528;&#xFF0C;&#x6240;&#x4EE5;&#x6700;&#x597D;&#x500D;&#x589E;&#x957F;&#x56E0;&#x5B50;&#x8BBE;&#x7F6E;&#x4E3A;1&#x548C;2&#x4E4B;&#x95F4;&#xFF0C;&#x5373;&#xFF08;1,2&#xFF09;</p>
<p>$$k\sum^n_{i=0}2^i = k(2^{n+1}-1)&lt;k2^{n+1}$$</p>
<h4 id="57---&#x9891;&#x7E41;&#x5BF9;vector&#x8C03;&#x7528;pushback&#x5BF9;&#x6027;&#x80FD;&#x7684;&#x5F71;&#x54CD;&#x548C;&#x539F;&#x56E0;&#xFF1F;">5.7 - &#x9891;&#x7E41;&#x5BF9;vector&#x8C03;&#x7528;push_back()&#x5BF9;&#x6027;&#x80FD;&#x7684;&#x5F71;&#x54CD;&#x548C;&#x539F;&#x56E0;&#xFF1F;</h4>
<p>&#x5728;&#x4E00;&#x4E2A;vector&#x7684;&#x5C3E;&#x90E8;&#x4E4B;&#x5916;&#x7684;&#x4EFB;&#x4F55;&#x4F4D;&#x7F6E;&#x6DFB;&#x52A0;&#x5143;&#x7D20;&#xFF0C;&#x90FD;&#x9700;&#x8981;&#x91CD;&#x65B0;&#x79FB;&#x52A8;&#x5143;&#x7D20;&#x3002;&#x800C;&#x4E14;&#xFF0C;&#x60F3;&#x4E00;&#x4E2A;vector&#x6DFB;&#x52A0;&#x5143;&#x7D20;&#x53EF;&#x80FD;&#x4F1A;&#x5F15;&#x8D77;&#x6574;&#x4E2A;&#x5BF9;&#x8C61;&#x5B58;&#x50A8;&#x7A7A;&#x95F4;&#x7684;&#x91CD;&#x65B0;&#x5206;&#x914D;&#x3002;&#x91CD;&#x65B0;&#x5206;&#x914D;&#x4E00;&#x4E2A;&#x5BF9;&#x8C61;&#x7684;&#x5B58;&#x50A8;&#x7A7A;&#x95F4;&#x9700;&#x8981;&#x5206;&#x914D;&#x65B0;&#x7684;&#x5185;&#x5B58;&#xFF0C;&#x5E76;&#x5C06;&#x5143;&#x7D20;&#x4ECE;&#x65E7;&#x7684;&#x7A7A;&#x95F4;&#x79FB;&#x5230;&#x65B0;&#x7684;&#x7A7A;&#x95F4;&#xFF0C;&#x5F71;&#x54CD;&#x6027;&#x80FD;&#x3002;</p>
<h3 id="6---list-&#x5E95;&#x5C42;&#x662F;&#x600E;&#x4E48;&#x5B9E;&#x73B0;&#x7684;&#xFF1F;list&#x76F8;&#x5173;&#x95EE;&#x9898;">6 - list &#x5E95;&#x5C42;&#x662F;&#x600E;&#x4E48;&#x5B9E;&#x73B0;&#x7684;&#xFF1F;list&#x76F8;&#x5173;&#x95EE;&#x9898;</h3>
<h4 id="60-list&#x5E95;&#x5C42;">6.0 list&#x5E95;&#x5C42;</h4>
<ul>
<li><p><strong>list&#x5E95;&#x5C42;&#x662F;&#x4E00;&#x4E2A;&#x53CC;&#x5411;&#x94FE;&#x8868;&#xFF0C;</strong>&#x4EE5;&#x8282;&#x70B9;&#x4E3A;&#x5355;&#x4F4D;&#x5B58;&#x653E;&#x6570;&#x636E;&#xFF0C;&#x7ED3;&#x70B9;&#x7684;&#x5730;&#x5740;&#x5728;&#x5185;&#x5B58;&#x4E2D;&#x4E0D;&#x4E00;&#x5B9A;&#x8FDE;&#x7EED;&#xFF0C;&#x6BCF;&#x6B21;&#x63D2;&#x5165;&#x6216;&#x5220;&#x9664;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#xFF0C;&#x5C31;&#x5206;&#x914D;&#x6216;&#x91CA;&#x653E;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x7A7A;&#x95F4;&#x3002;</p>
</li>
<li><p><strong>list&#x4E0D;&#x652F;&#x6301;&#x968F;&#x673A;&#x5B58;&#x53D6;&#xFF0C;</strong>&#x9002;&#x5408;&#x9700;&#x8981;&#x5927;&#x91CF;&#x7684;&#x63D2;&#x5165;&#x548C;&#x5220;&#x9664;&#xFF0C;&#x800C;&#x4E0D;&#x5173;&#x5FC3;&#x968F;&#x673A;&#x5B58;&#x53D6;&#x7684;&#x5E94;&#x7528;&#x573A;&#x666F;&#x3002;</p>
</li>
</ul>
<p><img src="https://gitee.com/song-zhuozhu/my_image/raw/master/img/image-20210910211801644.png" alt="image-20210910211801644" style="zoom: 50%;"></p>
<h4 id="61-list&#x5E38;&#x7528;&#x51FD;&#x6570;">6.1 list&#x5E38;&#x7528;&#x51FD;&#x6570;</h4>
<pre><code class="lang-cpp"><span class="hljs-built_in">list</span>.push_back(elem);
<span class="hljs-built_in">list</span>.pop_back();
<span class="hljs-built_in">list</span>.push_front(elem);
<span class="hljs-built_in">list</span>.size();
<span class="hljs-built_in">list</span>.sort();
<span class="hljs-built_in">list</span>.unique();   <span class="hljs-comment">// &#x79FB;&#x9664;&#x6570;&#x503C;&#x76F8;&#x540C;&#x7684;&#x8FDE;&#x7EED;&#x5143;&#x7D20;</span>
<span class="hljs-built_in">list</span>.back();     <span class="hljs-comment">// &#x53D6;&#x5C3E;&#x8FED;&#x4EE3;&#x5668;</span>
<span class="hljs-built_in">list</span>.erase(it);  <span class="hljs-comment">// &#x5220;&#x9664;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#xFF0C;&#x8FD4;&#x56DE;&#x5220;&#x9664;&#x5143;&#x7D20;&#x7684;&#x4E0B;&#x4E00;&#x4E2A;&#x8FED;&#x4EE3;&#x5668;</span>
</code></pre>
<h3 id="7---map&#x3001;set&#x3001;multiset&#x3001;multimap&#x5E95;&#x5C42;&#x662F;&#x600E;&#x4E48;&#x5B9E;&#x73B0;&#x7684;&#xFF1F;&#x53CA;&#x76F8;&#x5173;&#x95EE;&#x9898;">7 - map&#x3001;set&#x3001;multiset&#x3001;multimap&#x5E95;&#x5C42;&#x662F;&#x600E;&#x4E48;&#x5B9E;&#x73B0;&#x7684;&#xFF1F;&#x53CA;&#x76F8;&#x5173;&#x95EE;&#x9898;</h3>
<h4 id="70---map&#x3001;set&#x3001;multiset&#x3001;multimap&#x7684;&#x5E95;&#x5C42;&#x539F;&#x7406;">7.0 - map&#x3001;set&#x3001;multiset&#x3001;multimap&#x7684;&#x5E95;&#x5C42;&#x539F;&#x7406;</h4>
<p>map&#x3001;set&#x3001;multiset&#x3001;multimap&#x7684;&#x5E95;&#x5C42;&#x5B9E;&#x73B0;&#x90FD;&#x662F;&#x7EA2;&#x9ED1;&#x6811;&#xFF0C;epoll&#x6A21;&#x578B;&#x7684;&#x5E95;&#x5C42;&#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E5F;&#x662F;&#x7EA2;&#x9ED1;&#x6811;&#xFF0C;Linux&#x7CFB;&#x7EDF;&#x4E2D;CFS&#x8FDB;&#x7A0B;&#x8C03;&#x5EA6;&#x7B97;&#x6CD5;&#x4E5F;&#x7528;&#x5230;&#x4E86;&#x7EA2;&#x9ED1;&#x6811;</p>
<h4 id="71---&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x7279;&#x6027;&#xFF1A;">7.1 - &#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x7279;&#x6027;&#xFF1A;</h4>
<ul>
<li>&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x662F;&#x7EA2;&#x8272;&#x6216;&#x9ED1;&#x8272;&#x7684;</li>
<li>&#x6839;&#x8282;&#x70B9;&#x662F;&#x9ED1;&#x8272;&#x7684;</li>
<li>&#x6BCF;&#x4E2A;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#x662F;&#x9ED1;&#x8272;&#x7684;</li>
<li>&#x5982;&#x679C;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#x662F;&#x7EA2;&#x7684;&#xFF0C;&#x5219;&#x5B83;&#x7684;&#x4E24;&#x4E2A;&#x513F;&#x5B50;&#x5747;&#x662F;&#x9ED1;&#x8272;&#x7684;</li>
<li><strong>&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x5230;&#x5176;&#x5B50;&#x5B59;&#x8282;&#x70B9;NULL&#x6307;&#x9488;&#x7684;&#x6240;&#x6709;&#x8DEF;&#x5F84;&#x4E0A;&#x5305;&#x542B;&#x76F8;&#x540C;&#x6570;&#x76EE;&#x7684;&#x9ED1;&#x8272;&#x8282;&#x70B9;</strong></li>
</ul>
<p><a href="https://www.iamshuaidi.com/2061.html" target="_blank">&#x7EA2;&#x9ED1;&#x6811;&#x8BE6;&#x89E3;&#xFF1A;</a></p>
<h4 id="72---map&#x3001;set&#x3001;multiset&#x3001;multimap&#x7684;&#x7279;&#x70B9;">7.2 - map&#x3001;set&#x3001;multiset&#x3001;multimap&#x7684;&#x7279;&#x70B9;</h4>
<p>set&#x548C;multiset&#x4F1A;&#x6839;&#x636E;&#x7279;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x51C6;&#x5219;&#x81EA;&#x52A8;&#x5C06;&#x5143;&#x7D20;&#x6392;&#x5E8F;&#xFF0C;set&#x4E2D;&#x5143;&#x7D20;&#x4E0D;&#x91CD;&#x590D;&#xFF0C;multiset&#x53EF;&#x4EE5;&#x91CD;&#x590D;</p>
<p>map&#x548C;multimap&#x5C06; key &#x548C; value &#x7EC4;&#x6210;&#x7684; pair &#x4F5C;&#x4E3A;&#x5143;&#x7D20;&#xFF0C;&#x6839;&#x636E;key&#x7684;&#x6392;&#x5E8F;&#x51C6;&#x5219;&#x81EA;&#x52A8;&#x5C06;&#x5143;&#x7D20;&#x6392;&#x5E8F;&#xFF0C;map&#x4E2D;key&#x4E0D;&#x5141;&#x8BB8;&#x91CD;&#x590D;&#xFF0C;multimap&#x53EF;&#x4EE5;&#x91CD;&#x590D;</p>
<h4 id="73---&#x4E3A;&#x4F55;map&#x548C;set&#x7684;&#x63D2;&#x5165;&#x5220;&#x9664;&#x6548;&#x7387;&#x6BD4;&#x5176;&#x4ED6;&#x5E8F;&#x5217;&#x5BB9;&#x5668;&#x9AD8;&#xFF0C;&#x800C;&#x4E14;&#x6BCF;&#x6B21;insert&#x4E4B;&#x540E;&#xFF0C;&#x4EE5;&#x524D;&#x4FDD;&#x5B58;&#x7684;&#x8FED;&#x4EE3;&#x5668;&#x4E0D;&#x4F1A;&#x5931;&#x6548;&#xFF1F;">7.3 - &#x4E3A;&#x4F55;map&#x548C;set&#x7684;&#x63D2;&#x5165;&#x5220;&#x9664;&#x6548;&#x7387;&#x6BD4;&#x5176;&#x4ED6;&#x5E8F;&#x5217;&#x5BB9;&#x5668;&#x9AD8;&#xFF0C;&#x800C;&#x4E14;&#x6BCF;&#x6B21;insert&#x4E4B;&#x540E;&#xFF0C;&#x4EE5;&#x524D;&#x4FDD;&#x5B58;&#x7684;&#x8FED;&#x4EE3;&#x5668;&#x4E0D;&#x4F1A;&#x5931;&#x6548;&#xFF1F;</h4>
<p>&#x56E0;&#x4E3A;&#x5B58;&#x50A8;&#x7684;&#x662F;&#x8282;&#x70B9;&#xFF0C;&#x4E0D;&#x9700;&#x8981;&#x5185;&#x5B58;&#x7684;&#x62F7;&#x8D1D;&#x548C;&#x79FB;&#x52A8;</p>
<p>&#x56E0;&#x4E3A;&#x63D2;&#x5165;&#x64CD;&#x4F5C;&#x77E5;&#x8BC6;&#x8282;&#x70B9;&#x6307;&#x9488;&#x7684;&#x6362;&#x6765;&#x6362;&#x53BB;&#xFF0C;&#x8282;&#x70B9;&#x5185;&#x5B58;&#x6CA1;&#x6709;&#x6539;&#x53D8;&#x3002;&#x800C;&#x8FED;&#x4EE3;&#x5668;&#x5C31;&#x50CF;&#x6307;&#x5411;&#x8282;&#x70B9;&#x7684;&#x6307;&#x9488;&#xFF0C;&#x5185;&#x5B58;&#x6CA1;&#x53D8;&#xFF0C;&#x6307;&#x5411;&#x5185;&#x5B58;&#x7684;&#x6307;&#x9488;&#x4E5F;&#x4E0D;&#x4F1A;&#x53D8;&#x3002;</p>
<h4 id="74---&#x4E3A;&#x4F55;map&#x548C;set&#x4E0D;&#x80FD;&#x50CF;vector&#x4E00;&#x6837;&#x6709;&#x4E00;&#x4E2A;reserve&#x51FD;&#x6570;&#x6765;&#x9884;&#x5206;&#x914D;&#x6570;&#x636E;&#xFF1F;">7.4 - &#x4E3A;&#x4F55;map&#x548C;set&#x4E0D;&#x80FD;&#x50CF;vector&#x4E00;&#x6837;&#x6709;&#x4E00;&#x4E2A;reserve&#x51FD;&#x6570;&#x6765;&#x9884;&#x5206;&#x914D;&#x6570;&#x636E;&#xFF1F;</h4>
<p>&#x56E0;&#x4E3A;&#x5728;map&#x548C;set&#x5185;&#x90E8;&#x5B58;&#x50A8;&#x7684;&#x5DF2;&#x7ECF;&#x4E0D;&#x662F;&#x5143;&#x7D20;&#x672C;&#x8EAB;&#x4E86;&#xFF0C;&#x800C;&#x662F;&#x5305;&#x542B;&#x5143;&#x7D20;&#x7684;&#x8282;&#x70B9;&#x3002;&#x4E5F;&#x5C31;&#x662F;&#x8BF4;map&#x5185;&#x90E8;&#x4F7F;&#x7528;&#x7684;Alloc&#x5E76;&#x4E0D;&#x662F;map<key,data,compare,alloc>&#x58F0;&#x660E;&#x7684;&#x65F6;&#x5019;&#x4ECE;&#x53C2;&#x6570;&#x4F20;&#x5165;&#x7684;Alloc.</key,data,compare,alloc></p>
<h4 id="75---map&#x3001;set&#x3001;multiset&#x3001;multimap-&#x5E38;&#x7528;&#x51FD;&#x6570;&#xFF1F;">7.5 - map&#x3001;set&#x3001;multiset&#x3001;multimap &#x5E38;&#x7528;&#x51FD;&#x6570;&#xFF1F;</h4>
<pre><code class="lang-cpp">mp.count(key) &gt; <span class="hljs-number">0</span>;       <span class="hljs-comment">// &#x7EDF;&#x8BA1;&#x7684;&#x662F;key&#x51FA;&#x73B0;&#x7684;&#x6B21;&#x6570;&#xFF0C;&#x53EA;&#x80FD;&#x662F;0&#x6216;1</span>
mp.find(key) != mp.end() <span class="hljs-comment">//&#x8868;&#x793A;key&#x5B58;&#x5728;</span>

<span class="hljs-comment">// &#x5747;&#x8FD4;&#x56DE;&#x8FED;&#x4EE3;&#x5668;</span>
it <span class="hljs-built_in">map</span>.begin();
it <span class="hljs-built_in">map</span>.end();
it mp.find(k);

<span class="hljs-keyword">bool</span> <span class="hljs-built_in">map</span>.empty();
<span class="hljs-keyword">int</span> <span class="hljs-built_in">map</span>.size();
<span class="hljs-built_in">map</span>.insert({it,<span class="hljs-built_in">string</span>});

<span class="hljs-keyword">for</span> (it = mp.begin();it != mp.end())
{
    <span class="hljs-keyword">if</span> (it-&gt;second == <span class="hljs-string">&quot;target&quot;</span>)
        mp.erase(it++);
    <span class="hljs-keyword">else</span> ++it;
}
</code></pre>
<h3 id="8---unorderedmap&#x3001;unorderedset-&#x5E95;&#x5C42;&#x662F;&#x600E;&#x4E48;&#x5B9E;&#x73B0;&#x7684;&#xFF1F;">8 - unordered_map&#x3001;unordered_set &#x5E95;&#x5C42;&#x662F;&#x600E;&#x4E48;&#x5B9E;&#x73B0;&#x7684;&#xFF1F;</h3>
<h4 id="80---unorderedmap&#x3001;unorderedset-&#x5E95;&#x5C42;&#x539F;&#x7406;">8.0 - unordered_map&#x3001;unordered_set &#x5E95;&#x5C42;&#x539F;&#x7406;</h4>
<ul>
<li>unordered_map&#x7684;&#x5E95;&#x5C42;&#x662F;&#x4E00;&#x4E2A;&#x9632;&#x5197;&#x4F59;&#x7684;&#x54C8;&#x5E0C;&#x8868;&#xFF08;&#x91C7;&#x7528;&#x9664;&#x7559;&#x4F59;&#x6570;&#x6CD5;&#xFF09;&#x3002;&#x54C8;&#x5E0C;&#x8868;&#x6700;&#x5927;&#x7684;&#x4F18;&#x70B9;&#x5C31;&#x662F;&#x628A;&#x6570;&#x636E;&#x7684;&#x5B58;&#x50A8;&#x548C;&#x67E5;&#x627E;&#x5C0F;&#x53F7;&#x7684;&#x65F6;&#x95F4;&#x5927;&#x5927;&#x964D;&#x4F4E;&#xFF0C;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A;$O(1)$&#xFF1B;&#x800C;&#x4EE3;&#x4EF7;&#x662F;&#x6D88;&#x8017;&#x6BD4;&#x8F83;&#x591A;&#x7684;&#x5185;&#x5B58;</li>
<li>&#x4F7F;&#x7528;&#x4E00;&#x4E2A;&#x4E0B;&#x6807;&#x8303;&#x56F4;&#x6BD4;&#x8F83;&#x5927;&#x7684;&#x6570;&#x7EC4;&#x6765;&#x5B58;&#x50A8;&#x5143;&#x7D20;&#x3002;&#x8BBE;&#x8BA1;&#x54C8;&#x5E0C;&#x51FD;&#x6570;&#xFF08;&#x4E00;&#x822C;&#x4F7F;&#x7528;&#x9664;&#x7559;&#x4F59;&#x6570;&#x6CD5;&#xFF09;&#xFF0C;&#x4F7F;&#x5F97;&#x6BCF;&#x4E2A;&#x5143;&#x7D20;&#x7684;key&#x90FD;&#x4E0E;&#x4E00;&#x4E2A;&#x51FD;&#x6570;&#x503C;&#xFF08;&#x5373;&#x6570;&#x7EC4;&#x4E0B;&#x6807;&#xFF0C;hash&#x503C;&#xFF09;&#x76F8;&#x5BF9;&#x5E94;&#xFF0C;&#x4E8E;&#x662F;&#x8FD9;&#x4E2A;&#x6570;&#x7EC4;&#x5355;&#x5143;&#x7528;&#x6765;&#x5B58;&#x50A8;&#x8FD9;&#x4E2A;&#x5143;&#x7D20;&#xFF0C;&#x8FD9;&#x4E2A;&#x6570;&#x7EC4;&#x5355;&#x5143;&#x4E00;&#x822C;&#x79F0;&#x4E3A;&#x6876;&#x3002;</li>
<li>&#x4E0D;&#x80FD;&#x4FDD;&#x8BC1;&#x6BCF;&#x4E2A;&#x5143;&#x7D20;&#x7684;key&#x4E0E;&#x51FD;&#x6570;&#x503C;&#x662F;&#x4E00;&#x4E00;&#x5BF9;&#x5E94;&#x7684;&#xFF0C;&#x56E0;&#x6B64;&#x6781;&#x6709;&#x53EF;&#x80FD;&#x51FA;&#x73B0;&#x5BF9;&#x4E8E;&#x4E0D;&#x540C;&#x7684;&#x5143;&#x7D20;&#xFF0C;&#x5374;&#x8BA1;&#x7B97;&#x51FA;&#x4E86;&#x76F8;&#x540C;&#x7684;&#x51FD;&#x6570;&#x503C;&#xFF0C;&#x8FD9;&#x5C31;&#x4EA7;&#x751F;&#x4E86;&#x51B2;&#x7A81;&#xFF0C;&#x4E00;&#x822C;&#x7528;&#x5F00;&#x94FE;&#x6CD5;&#x89E3;&#x51B3;&#x51B2;&#x7A81;</li>
</ul>
<h4 id="81-unorderedmap-&#x548C;-map&#x7684;&#x533A;&#x522B;&#xFF1F;&#x4F7F;&#x7528;&#x573A;&#x666F;&#xFF1F;">8.1 unordered_map &#x548C; map&#x7684;&#x533A;&#x522B;&#xFF1F;&#x4F7F;&#x7528;&#x573A;&#x666F;&#xFF1F;</h4>
<ul>
<li>&#x6784;&#x9020;&#x51FD;&#x6570;&#xFF1A;unordered_map &#x9700;&#x8981;hash&#x51FD;&#x6570;&#xFF0C;&#x7B49;&#x4E8E;&#x51FD;&#x6570;&#xFF1B;map&#x53EA;&#x9700;&#x8981;&#x6BD4;&#x8F83;&#xFF08;&#x5C0F;&#x4E8E;&#xFF09;&#x51FD;&#x6570;</li>
<li>&#x5B58;&#x50A8;&#x7ED3;&#x6784;&#xFF1A;unordered_map &#x91C7;&#x7528;hash&#x8868;&#x5B58;&#x50A8;&#xFF0C;map&#x4E00;&#x822C;&#x91C7;&#x7528;&#x7EA2;&#x9ED1;&#x6811;&#xFF08;RB Tree&#xFF09;&#x5B9E;&#x73B0;&#x3002;&#x56E0;&#x6B64;&#x5176;memory&#x6570;&#x636E;&#x7ED3;&#x6784;&#x4E0A;&#x4E0D;&#x4E00;&#x6837;&#x7684;&#x3002;</li>
<li>&#x603B;&#x4F53;&#x6765;&#x8BF4;&#xFF0C;unordered_map&#x67E5;&#x627E;&#x901F;&#x5EA6;&#x6BD4;map&#x5FEB;&#xFF0C;&#x5C5E;&#x4E8E;&#x5E38;&#x6570;&#x7EA7;&#x522B;&#xFF1B;&#x800C;map&#x7684;&#x67E5;&#x627E;&#x901F;&#x5EA6;&#x4E0A;&#x662F; $\log{n}$ &#x7EA7;&#x522B;&#x3002; &#x4F46;&#x662F;&#x5E76;&#x4E0D;&#x4E00;&#x5B9A;&#x5E38;&#x6570;&#x5C31;&#x6BD4;$\log{n}$ &#x5C0F;&#xFF0C;hash&#x8FD8;&#x6709;hash&#x51FD;&#x6570;&#x7684;&#x8017;&#x65F6;&#x3002;&#x5F53;&#x5143;&#x7D20;&#x8FBE;&#x5230;&#x4E00;&#x5B9A;&#x7684;&#x6570;&#x91CF;&#x7EA7;&#x65F6;&#xFF0C;&#x4F18;&#x5148;&#x8003;&#x8651;hash_map&#xFF1B;&#x82E5;&#x5BF9;&#x5185;&#x5B58;&#x4F7F;&#x7528;&#x91CF;&#x6709;&#x4E25;&#x683C;&#x8981;&#x6C42;&#xFF0C;hash_map&#x9700;&#x8981;&#x614E;&#x9009;&#xFF0C;&#x800C;&#x4E14;hash_map&#x6784;&#x9020;&#x901F;&#x5EA6;&#x8F83;&#x6162;&#x3002;&#x6240;&#x4EE5;&#x5982;&#x4F55;&#x9009;&#x62E9;&#xFF0C;&#x4E3B;&#x8981;&#x6743;&#x8861;&#x4E09;&#x4E2A;&#x56E0;&#x7D20;&#xFF1A;&#x67E5;&#x627E;&#x901F;&#x5EA6;&#x3001;&#x6570;&#x636E;&#x91CF;&#x3001;&#x5185;&#x5B58;&#x4F7F;&#x7528;</li>
</ul>
<h4 id="82-unorderedmap&#x3001;unorderedset&#x5E38;&#x7528;&#x51FD;&#x6570;&#x6709;&#x54EA;&#x4E9B;&#xFF1F;">8.2 unordered_map&#x3001;unordered_set&#x5E38;&#x7528;&#x51FD;&#x6570;&#x6709;&#x54EA;&#x4E9B;&#xFF1F;</h4>
<pre><code class="lang-cpp"><span class="hljs-built_in">unordered_map</span>.begin();   <span class="hljs-comment">// &#x8D77;&#x59CB;&#x4F4D;&#x7F6E;&#x8FED;&#x4EE3;&#x5668;</span>
<span class="hljs-built_in">unordered_map</span>.end();       <span class="hljs-comment">// &#x672B;&#x5C3E;&#x8FED;&#x4EE3;&#x5668;</span>
<span class="hljs-built_in">unordered_map</span>.cbegin();  <span class="hljs-comment">// &#x8D77;&#x59CB;&#x4F4D;&#x7F6E;&#x5E38;&#x8FED;&#x4EE3;&#x5668; const_iterator</span>
<span class="hljs-built_in">unordered_map</span>.cend();    <span class="hljs-comment">// &#x672B;&#x5C3E;&#x5E38;&#x8FED;&#x4EE3;&#x5668;</span>
<span class="hljs-built_in">unordered_map</span>.size();    <span class="hljs-comment">// &#x6709;&#x6548;&#x5143;&#x7D20;&#x4E2A;&#x6570;</span>
<span class="hljs-built_in">unordered_map</span>.insert(key); <span class="hljs-comment">// &#x63D2;&#x5165;&#x5143;&#x7D20;</span>
<span class="hljs-built_in">unordered_map</span>.find(key);   <span class="hljs-comment">// &#x67E5;&#x627E;&#x5143;&#x7D20;&#xFF0C;&#x8FD4;&#x56DE;&#x8FED;&#x4EE3;&#x5668;</span>
<span class="hljs-built_in">unordered_map</span>.count(key);  <span class="hljs-comment">// &#x8FD4;&#x56DE;&#x5339;&#x914D;&#x7ED9;&#x5B9A;&#x4E3B;&#x952E;&#x7684;&#x5143;&#x7D20;&#x7684;&#x4E2A;&#x6570;</span>
</code></pre>
<h3 id="9---&#x8FED;&#x4EE3;&#x5668;&#x7684;&#x5E95;&#x5C42;&#x673A;&#x5236;&#x548C;&#x5931;&#x6548;&#x95EE;&#x9898;">9 - &#x8FED;&#x4EE3;&#x5668;&#x7684;&#x5E95;&#x5C42;&#x673A;&#x5236;&#x548C;&#x5931;&#x6548;&#x95EE;&#x9898;</h3>
<h4 id="90---&#x8FED;&#x4EE3;&#x5668;&#x7684;&#x5E95;&#x5C42;&#x539F;&#x7406;">9.0 - &#x8FED;&#x4EE3;&#x5668;&#x7684;&#x5E95;&#x5C42;&#x539F;&#x7406;</h4>
<p>&#x8FED;&#x4EE3;&#x5668;&#x4E0A;&#x8FDE;&#x63A5;&#x5BB9;&#x5668;&#x548C;&#x7B97;&#x6CD5;&#x7684;&#x4E00;&#x4E2A;&#x6865;&#x6881;&#xFF0C;&#x901A;&#x8FC7;&#x8FED;&#x4EE3;&#x5668;&#x53EF;&#x4EE5;&#x5728;&#x4E0D;&#x4E86;&#x89E3;&#x5BB9;&#x5668;&#x7684;&#x5185;&#x90E8;&#x539F;&#x7406;&#x7684;&#x60C5;&#x51B5;&#x4E0B;&#x904D;&#x5386;&#x5BB9;&#x5668;&#x3002;</p>
<p>&#x5B83;&#x7684;&#x5E95;&#x5C42;&#x5B9E;&#x73B0;&#x5305;&#x542B;&#x4E24;&#x4E2A;&#x91CD;&#x8981;&#x7684;&#x90E8;&#x5206;&#xFF1A;</p>
<ul>
<li>&#x8403;&#x53D6;&#x6280;&#x672F;</li>
<li>&#x6A21;&#x677F;&#x4FBF;&#x7279;&#x5316;</li>
</ul>
<p>&#x8403;&#x53D6;&#x6280;&#x672F;&#xFF08;traits&#xFF09;&#x53EF;&#x4EE5;&#x8FDB;&#x884C;&#x7C7B;&#x578B;&#x63A8;&#x5BFC;&#xFF0C;&#x6839;&#x636E;&#x4E0D;&#x540C;&#x7C7B;&#x578B;&#x53EF;&#x4EE5;&#x6267;&#x884C;&#x4E0D;&#x540C;&#x7684;&#x5904;&#x7406;&#x6D41;&#x7A0B;&#xFF0C;&#x6BD4;&#x5982;&#x5BB9;&#x5668;&#x662F;vector&#xFF0C;&#x90A3;&#x4E48;traits&#x5FC5;&#x987B;&#x63A8;&#x5BFC;&#x51FA;&#x5176;&#x8FED;&#x4EE3;&#x5668;&#x7C7B;&#x578B;&#x4F4D;&#x968F;&#x673A;&#x8BBF;&#x95EE;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x800C;list&#x5219;&#x4F4D;&#x53CC;&#x5411;&#x8FED;&#x4EE3;&#x5668;&#x3002;</p>
<ul>
<li>&#x4F8B;&#x5982;STL&#x7B97;&#x6CD5;&#x5E93;&#x4E2D;&#x7684;distance&#x51FD;&#x6570;&#xFF0C;distance&#x51FD;&#x6570;&#x63A5;&#x53D7;&#x4E24;&#x4E2A;&#x8FED;&#x4EE3;&#x5668;&#x53C2;&#x6570;&#xFF0C;&#x7136;&#x540E;&#x8BA1;&#x7B97;&#x4ED6;&#x4EEC;&#x4E24;&#x8005;&#x4E4B;&#x95F4;&#x7684;&#x8DDD;&#x79BB;&#x3002;&#x663E;&#x7136;&#x5BF9;&#x4E8E;&#x4E0D;&#x540C;&#x7684;&#x8FED;&#x4EE3;&#x5668;&#x8BA1;&#x7B97;&#x6548;&#x7387;&#x5DEE;&#x522B;&#x5F88;&#x5927;&#x3002;&#x6BD4;&#x5982;&#x5BF9;&#x4E8E;vector&#x5BB9;&#x5668;&#x6765;&#x8BF4;&#xFF0C;&#x5BF9;&#x4E8E;&#x5185;&#x5B58;&#x662F;&#x8FDE;&#x7EED;&#x5206;&#x914D;&#x7684;&#xFF0C;&#x56E0;&#x6B64;&#x6307;&#x9488;&#x76F4;&#x63A5;&#x76F8;&#x51CF;&#x5373;&#x53EF;&#x83B7;&#x5F97;&#x4E24;&#x8005;&#x7684;&#x8DDD;&#x79BB;&#xFF1B;&#x800C;list&#x5BB9;&#x5668;&#x662F;&#x94FE;&#x5F0F;&#x8868;&#xFF0C;&#x5185;&#x5B58;&#x4E00;&#x822C;&#x90FD;&#x4E0D;&#x662F;&#x8FDE;&#x7EED;&#x5206;&#x914D;&#xFF0C;&#x56E0;&#x6B64;&#x53EA;&#x80FD;&#x901A;&#x8FC7;&#x4E00;&#x7EA7;&#x4E00;&#x7EA7;&#x8C03;&#x7528;next() &#x6216; &#x5176;&#x4ED6;&#x51FD;&#x6570;&#xFF0C;&#x6CA1;&#x8C03;&#x7528;&#x4E00;&#x6B21;&#x518D;&#x5224;&#x65AD;&#x8FED;&#x4EE3;&#x5668;&#x662F;&#x5426;&#x76F8;&#x7B49;&#x6765;&#x8BA1;&#x7B97;&#x8DDD;&#x79BB;&#x3002;vector&#x8FED;&#x4EE3;&#x5668;&#x8BA1;&#x7B97;distance&#x7684;&#x6548;&#x7387;&#x4E3A;$O(1)$ ,&#x800C;list&#x5219;&#x4E3A;$O(n)$, n&#x4E3A;&#x8DDD;&#x79BB;&#x7684;&#x5927;&#x5C0F;&#x3002;</li>
<li>&#x4F7F;&#x7528;&#x8403;&#x53D6;&#x6280;&#x672F;&#xFF08;traits&#xFF09;&#x8FDB;&#x884C;&#x7C7B;&#x578B;&#x63A8;&#x5BFC;&#x7684;&#x8FC7;&#x7A0B;&#x4E2D;&#x4F1A;&#x4F7F;&#x7528;&#x5230;&#x6A21;&#x677F;&#x504F;&#x7279;&#x5316;&#x3002;&#x6A21;&#x677F;&#x504F;&#x7279;&#x5316;&#x53EF;&#x4EE5;&#x7528;&#x6765;&#x63A8;&#x5BFC;&#x53C2;&#x6570;&#xFF0C;&#x5982;&#x679C;&#x6211;&#x4EEC;&#x81EA;&#x5B9A;&#x4E49;&#x591A;&#x4E2A;&#x7C7B;&#x578B;&#xFF0C;&#x9664;&#x975E;&#x6211;&#x4EEC;&#x628A;&#x8FD9;&#x4E9B;&#x81EA;&#x5B9A;&#x4E49;&#x7C7B;&#x578B;&#x7684;&#x7279;&#x5316;&#x7248;&#x672C;&#x5199;&#x51FA;&#x6765;&#xFF0C;&#x5426;&#x5219;&#x6211;&#x4EEC;&#x53EA;&#x80FD;&#x5224;&#x65AD;&#x4ED6;&#x4EEC;&#x662F;&#x5185;&#x7F6E;&#x7C7B;&#x578B;&#xFF0C;&#x5E76;&#x4E0D;&#x80FD;&#x5224;&#x65AD;&#x4ED6;&#x4EEC;&#x5177;&#x4F53;&#x5C5E;&#x4E8E;&#x54EA;&#x4E2A;&#x7C7B;&#x578B;&#x3002;</li>
</ul>
<pre><code class="lang-cpp"><span class="hljs-keyword">template</span> &lt;<span class="hljs-keyword">typename</span> T&gt;
<span class="hljs-keyword">struct</span> TraitsHelper
{
  <span class="hljs-keyword">static</span> <span class="hljs-keyword">const</span> <span class="hljs-keyword">bool</span> isPointer = <span class="hljs-literal">false</span>;
};
<span class="hljs-keyword">template</span> &lt;<span class="hljs-keyword">typename</span> T&gt;
<span class="hljs-keyword">struct</span> TraitsHelper&lt;T*&gt;
{
  <span class="hljs-keyword">static</span> <span class="hljs-keyword">const</span> <span class="hljs-keyword">bool</span> isPointer = <span class="hljs-literal">true</span>;
}

<span class="hljs-keyword">if</span> (TraitsHelper&lt;T&gt;::isPointer)
   .... <span class="hljs-comment">// &#x53EF;&#x4EE5;&#x5F97;&#x51FA;&#x5F53;&#x524D;&#x7C7B;&#x578B;int*&#x4E3A;&#x6307;&#x9488;&#x7C7B;&#x578B;</span>
<span class="hljs-keyword">else</span>
   .... <span class="hljs-comment">// &#x53EF;&#x4EE5;&#x5F97;&#x51FA;&#x5F53;&#x524D;&#x7C7B;&#x578B;int&#x975E;&#x6307;&#x9488;&#x7C7B;&#x578B;</span>
</code></pre>
<h4 id="91---&#x8FED;&#x4EE3;&#x5668;&#x7684;&#x79CD;&#x7C7B;">9.1 - &#x8FED;&#x4EE3;&#x5668;&#x7684;&#x79CD;&#x7C7B;</h4>
<ul>
<li>&#x8F93;&#x5165;&#x8FED;&#x4EE3;&#x5668;&#xFF1A;&#x662F;&#x53EA;&#x8BFB;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x5728;&#x6BCF;&#x4E2A;&#x88AB;&#x904D;&#x5386;&#x7684;&#x4F4D;&#x7F6E;&#x4E0A;&#x53EA;&#x80FD;&#x8BFB;&#x53D6;&#x4E00;&#x6B21;&#x3002;&#x5982;find&#x51FD;&#x6570;&#x7684;&#x53C2;&#x6570;&#x5C31;&#x662F;&#x8F93;&#x5165;&#x8FED;&#x4EE3;&#x5668;</li>
<li>&#x8F93;&#x51FA;&#x8FED;&#x4EE3;&#x5668;&#xFF1A;&#x662F;&#x53EA;&#x5199;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x5728;&#x6BCF;&#x4E2A;&#x88AB;&#x904D;&#x5386;&#x7684;&#x4F4D;&#x7F6E;&#x4E0A;&#x53EA;&#x80FD;&#x88AB;&#x5199;&#x4E00;&#x6B21;&#x3002;</li>
<li>&#x524D;&#x5411;&#x8FED;&#x4EE3;&#x5668;&#xFF1A;&#x517C;&#x5177;&#x6709;&#x8F93;&#x5165;&#x548C;&#x8F93;&#x51FA;&#x8FED;&#x4EE3;&#x5668;&#x7684;&#x80FD;&#x529B;&#xFF0C;&#x4F46;&#x662F;&#x5B83;&#x53EF;&#x4EE5;&#x5BF9;&#x540C;&#x4E00;&#x4E2A;&#x4F4D;&#x7F6E;&#x91CD;&#x9022;&#x8FDB;&#x884C;&#x8BFB;&#x548C;&#x5199;&#x3002;&#x4F46;&#x5B83;&#x4E0D;&#x652F;&#x6301;operator-&#xFF0C;&#x6240;&#x4EE5;&#x53EA;&#x80FD;&#x5411;&#x524D;&#x79FB;&#x52A8;&#x3002;</li>
<li>&#x53CC;&#x5411;&#x8FED;&#x4EE3;&#x5668;&#xFF1A;&#x5F88;&#x50CF;&#x524D;&#x5411;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x53EA;&#x662F;&#x5B83;&#x5411;&#x540E;&#x79FB;&#x52A8;&#x548C;&#x5411;&#x524D;&#x79FB;&#x52A8;&#x540C;&#x6837;&#x5BB9;&#x6613;</li>
<li>&#x968F;&#x673A;&#x8BBF;&#x95EE;&#x8FED;&#x4EE3;&#x5668;&#xFF1A;&#x6709;&#x53CC;&#x5411;&#x8FED;&#x4EE3;&#x5668;&#x7684;&#x6240;&#x6709;&#x529F;&#x80FD;&#x3002;&#x800C;&#x4E14;&#x8FD8;&#x63D0;&#x4F9B;&#x201C;&#x8FED;&#x4EE3;&#x5668;&#x7B97;&#x6570;&#x201D;&#xFF0C;&#x5373;&#x4E00;&#x6B65;&#x5185;&#x53EF;&#x4EE5;&#x5411;&#x524D;&#x6216;&#x5411;&#x540E;&#x8DF3;&#x8DC3;&#x4EFB;&#x610F;&#x4F4D;&#x7F6E;&#xFF0C;&#x5305;&#x542B;&#x6307;&#x9488;&#x7684;&#x6240;&#x6709;&#x64CD;&#x4F5C;&#x3002;&#x5E76;&#x53E6;&#x5916;&#x652F;&#x6301;it+n&#x3001;it-n&#x3001;it+=n&#x3001;it-=n&#x3001;it1-it2 &#x548C; it[n]&#x7B49;&#x64CD;&#x4F5C;&#x3002;</li>
</ul>
<h4 id="92---&#x8FED;&#x4EE3;&#x5668;&#x7684;&#x5931;&#x6548;&#x95EE;&#x9898;">9.2 - &#x8FED;&#x4EE3;&#x5668;&#x7684;&#x5931;&#x6548;&#x95EE;&#x9898;</h4>
<p>&#xFF08;1&#xFF09;&#x63D2;&#x5165;&#x64CD;&#x4F5C;&#xFF1A;</p>
<p>&#x5BF9;&#x4E8E;vector&#x548C;string&#x6765;&#x8BF4;&#xFF0C;&#x5982;&#x679C;&#x5BB9;&#x5668;&#x5185;&#x5B58;&#x88AB;&#x91CD;&#x65B0;&#x5206;&#x914D;&#x3002;&#x5219;&#x8FED;&#x4EE3;&#x5668;&#xFF08;iterators&#xFF09;&#x3001;pointers&#xFF08;&#x6307;&#x9488;&#xFF09;&#x3001;references&#xFF08;&#x5F15;&#x7528;&#xFF09;&#x90FD;&#x5931;&#x6548;&#xFF1B;&#x5982;&#x679C;&#x6CA1;&#x6709;&#x91CD;&#x65B0;&#x5206;&#x914D;&#xFF0C;&#x90A3;&#x4E48;&#x63D2;&#x5165;&#x70B9;&#x4E4B;&#x524D;&#x7684;iterator&#x6709;&#x6548;&#xFF0C; &#x63D2;&#x5165;&#x8282;&#x70B9;&#x4E4B;&#x540E;&#x7684;iterator&#x5931;&#x6548;&#xFF1B;</p>
<p>&#x5BF9;&#x4E8E;deque&#xFF0C;&#x5982;&#x679C;&#x63D2;&#x5165;&#x70B9;&#x4F4D;&#x4E8E;front&#x548C;back&#x7684;&#x5176;&#x4ED6;&#x4F4D;&#x7F6E;&#xFF0C;iterator&#x3001;pointers&#x3001;references&#x5931;&#x6548;&#xFF1B;&#x5F53;&#x63D2;&#x5165;&#x5143;&#x7D20;&#x5230;front&#x548C;back&#x65F6;&#xFF0C;deque&#x7684;&#x8FED;&#x4EE3;&#x5668;&#x5931;&#x6548;&#xFF0C;&#x4F46;references&#x548C;pointers&#x6709;&#x6548;&#x3002;</p>
<p>&#x5BF9;&#x4E8E;list&#x548C;forward_list&#xFF0C;&#x6240;&#x6709;&#x7684;iterator&#x3001;pointers&#x3001;references&#x90FD;&#x6709;&#x6548;&#x3002;</p>
<p>&#xFF08;2&#xFF09;&#x5220;&#x9664;&#x64CD;&#x4F5C;</p>
<p>&#x5BF9;&#x4E8E;vector&#x548C;string&#xFF0C;&#x5220;&#x9664;&#x8282;&#x70B9;&#x4E4B;&#x524D;&#x7684;iterators&#x3001;pointers&#x3001;references&#x6709;&#x6548;&#xFF1B;off_the_end&#x8FED;&#x4EE3;&#x5668;&#x603B;&#x662F;&#x5931;&#x6548;&#x7684;&#xFF1B;</p>
<p>&#x5BF9;&#x4E8E;deque&#xFF0C;&#x5982;&#x679C;&#x5220;&#x9664;&#x8282;&#x70B9;&#x4F4D;&#x7F6E;&#x9664;front&#x548C;back&#x7684;&#x5176;&#x4ED6;&#x4F4D;&#x7F6E;&#xFF0C;iterators&#x3001;pointers&#x3001;references&#x5931;&#x6548;&#xFF1B;&#x5F53;&#x63D2;&#x5165;&#x5143;&#x7D20;&#x5230;front&#x548C;back&#x65F6;&#xFF0C;off_the_end&#x5931;&#x6548;&#xFF0C;&#x5176;&#x4ED6;&#x7684;iterators&#x3001;pointers&#x3001;references&#x6709;&#x6548;&#x3002;</p>
<p>&#x5BF9;&#x4E8E;list&#x548C;forward_list&#xFF0C;&#x6240;&#x9047;&#x7684;iterator&#x3001;pointers&#x3001;references&#x6709;&#x6548;&#x3002;</p>
<p>&#x5BF9;&#x4E8E;&#x5173;&#x8054;&#x5BB9;&#x5668;map&#x6765;&#x8BF4;&#xFF0C;&#x5982;&#x679C;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x5DF2;&#x7ECF;&#x88AB;&#x5220;&#x9664;&#xFF0C;&#x90A3;&#x4E48;&#x5176;&#x5BF9;&#x5E94;&#x7684;&#x8FED;&#x4EE3;&#x5668;&#x5C31;&#x662F;&#x5931;&#x6548;&#x4E86;&#xFF0C;&#x4E0D;&#x5E94;&#x8BE5;&#x518D;&#x88AB;&#x4F7F;&#x7528;&#xFF0C;&#x5426;&#x5219;&#x4F1A;&#x5BFC;&#x81F4;&#x7A0B;&#x5E8F;&#x65E0;&#x5B9A;&#x4E49;&#x7684;&#x884C;&#x4E3A;&#x3002;</p>
<h3 id="10---deque&#x5E95;&#x5C42;&#x662F;&#x600E;&#x4E48;&#x5B9E;&#x73B0;&#x7684;&#xFF1F;">10 - deque&#x5E95;&#x5C42;&#x662F;&#x600E;&#x4E48;&#x5B9E;&#x73B0;&#x7684;&#xFF1F;</h3>
<h4 id="100-deque&#x7684;&#x5E95;&#x5C42;&#x539F;&#x7406;">10.0 deque&#x7684;&#x5E95;&#x5C42;&#x539F;&#x7406;</h4>
<p>deque&#x662F;&#x53CC;&#x7AEF;&#x961F;&#x5217;&#xFF0C;&#x5728;&#x5934;&#x5C3E;&#x8FDB;&#x884C;&#x63D2;&#x5165;&#x548C;&#x5220;&#x9664;&#x90FD;&#x662F;O(1)&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;</p>
<p>deque&#x7684;&#x5E95;&#x5C42;&#x5219;&#x662F;<strong>&#x82E5;&#x5E72;&#x4E2A;</strong>&#x6570;&#x7EC4;&#x7684;&#x96C6;&#x5408;&#xFF0C;&#x5355;&#x4E2A;&#x6570;&#x7EC4;&#x5185;&#x662F;&#x8FDE;&#x7EED;&#x7269;&#x7406;&#x7A7A;&#x95F4;&#xFF0C;&#x4F46;&#x4E0D;&#x540C;&#x6570;&#x7EC4;&#x95F4;&#x5374;&#x4E0D;&#x8FDE;&#x7EED;&#xFF1B;</p>
<p>deque&#x7684;&#x52A8;&#x6001;&#x62D3;&#x5C55;&#x6216;&#x52A8;&#x6001;&#x7F29;&#x51CF;&#xFF0C;&#x662F;&#x901A;&#x8FC7;&#x65B0;&#x589E;&#x6216;&#x8005;&#x91CA;&#x653E;&#x7269;&#x7406;&#x7A7A;&#x95F4;&#x7247;&#x6BB5;&#x6765;&#x5B9E;&#x73B0;&#x7684;&#xFF0C;&#x4E0D;&#x53D1;&#x751F;&#x6570;&#x636E;&#x7684;&#x8F6C;&#x79FB;&#x3002;</p>
<p>deque&#x5185;&#x90E8;&#x7EF4;&#x62A4;&#x4E86;&#x6240;&#x6709;&#x5143;&#x7D20;&#x7684;&#x5FC5;&#x8981;&#x4FE1;&#x606F;&#xFF0C;&#x4FDD;&#x8BC1;&#x80FD;&#x591F;&#x901A;&#x8FC7;&#x7EDF;&#x4E00;&#x7684;&#x63A5;&#x53E3;&#x76F4;&#x63A5;&#x8BBF;&#x95EE;&#x6240;&#x6709;&#x7684;&#x5143;&#x7D20;&#xFF0C;&#x4E14;&#x8BBF;&#x95EE;&#x8017;&#x65F6;&#x76F8;&#x7B49;&#xFF0C;&#x8BBF;&#x95EE;&#x8005;&#x65E0;&#x9700;&#x5173;&#x5FC3;&#x5404;&#x4E2A;&#x5143;&#x7D20;&#x662F;&#x5426;&#x4F4D;&#x4E8E;&#x540C;&#x4E00;&#x4E2A;&#x7269;&#x7406;&#x7A7A;&#x95F4;&#x4E0A;&#x3002;deque&#x7684;&#x5E95;&#x5C42;&#x8BBE;&#x8BA1;&#x51B3;&#x5B9A;&#x4E86;deque&#x7684;&#x4EE5;&#x4E0B;&#x7279;&#x6027;&#xFF1A;</p>
<ul>
<li>&#x2460; <strong>&#x652F;&#x6301;&#x9AD8;&#x6548;&#x7684;&#x53CC;&#x7AEF;&#x589E;&#x51CF;&#x64CD;&#x4F5C;</strong>&#xFF08;&#x56E0;&#x4E3A;&#x65E0;&#x9700;&#x79FB;&#x52A8;&#x6570;&#x636E;&#xFF09;</li>
<li>&#x2461; <strong>&#x5728;&#x5143;&#x7D20;&#x6570;&#x91CF;&#x5F88;&#x5927;&#x65F6;&#xFF0C;&#x603B;&#x4F53;&#x6765;&#x8BF4;&#x6BD4;vector&#x66F4;&#x9AD8;&#x6548;</strong>&#xFF08;&#x5927;&#x91CF;&#x6570;&#x636E;&#x7684;&#x79FB;&#x52A8;&#x5F88;&#x8017;&#x65F6;&#xFF09;</li>
<li>&#x2462; <strong>&#x4E0D;&#x652F;&#x6301;&#x201C;&#x6307;&#x9488;+offset&#x201D;&#x7684;&#x8BBF;&#x95EE;&#x65B9;&#x5F0F;</strong>&#xFF08;&#x7269;&#x7406;&#x7A7A;&#x95F4;&#x4E0D;&#x8FDE;&#x7EED;&#xFF09;</li>
<li>&#x2463; &#x5F53;&#x9700;&#x8981;&#x5728;&#x9996;&#x5C3E;&#x4E4B;&#x5916;&#x7684;&#x4F4D;&#x7F6E;&#x9891;&#x7E41;&#x63D2;&#x5165;/&#x79FB;&#x9664;&#x5143;&#x7D20;&#x65F6;&#xFF0C;deque&#x6BD4;list/forward_list&#x8868;&#x73B0;&#x66F4;&#x5DEE;&#x3002;</li>
<li>&#x2464; &#x8FED;&#x4EE3;&#x5668;&#x8BBF;&#x95EE;&#x6216;&#x8005;&#x5F15;&#x7528;&#x8BBF;&#x95EE;&#x7684;&#x8FDE;&#x7EED;&#x6027;&#x4E0D;&#x5982; list &#x548C; forward_list&#x3002;</li>
</ul>
<h4 id="101-deque&#x5E38;&#x7528;&#x51FD;&#x6570;">10.1 deque&#x5E38;&#x7528;&#x51FD;&#x6570;</h4>
<pre><code class="lang-cpp"><span class="hljs-built_in">deque</span>.push_back(elem);
<span class="hljs-built_in">deque</span>.pop_back();
<span class="hljs-built_in">deque</span>.push_front(elem);
<span class="hljs-built_in">deque</span>.pop_front();
<span class="hljs-built_in">deque</span>.size();
<span class="hljs-built_in">deque</span>.at(idx)  <span class="hljs-comment">// &#x4F20;&#x56DE;&#x7D22;&#x5F15;idx&#x6240;&#x6307;&#x7684;&#x6570;&#x636E;&#xFF0C;&#x5982;&#x679C;idx&#x8D8A;&#x754C;&#xFF0C;&#x629B;&#x51FA;out_of_range</span>
</code></pre>
<h3 id="11---vector-&#x548C;-list-&#x7684;&#x533A;&#x522B;&#x662F;&#x4EC0;&#x4E48;&#xFF1F;">11 - vector &#x548C; list &#x7684;&#x533A;&#x522B;&#x662F;&#x4EC0;&#x4E48;&#xFF1F;</h3>
<h4 id="vector">vector</h4>
<ul>
<li>&#x662F;&#x8FDE;&#x7EED;&#x5B58;&#x50A8;&#x7684;&#x5BB9;&#x5668;&#xFF0C;&#x52A8;&#x6001;&#x6570;&#x7EC4;&#xFF0C;&#x5728;&#x5806;&#x4E0A;&#x5206;&#x914D;&#x7A7A;&#x95F4;</li>
<li>&#x5E95;&#x5C42;&#x5B9E;&#x73B0;&#xFF1A;&#x6570;&#x7EC4;</li>
<li>&#x4E24;&#x500D;&#x5BB9;&#x91CF;&#x589E;&#x957F;&#xFF1A;<ul>
<li>vector &#x589E;&#x52A0;&#xFF08;&#x63D2;&#x5165;&#xFF09;&#x65B0;&#x5143;&#x7D20;&#x65F6;&#xFF0C;&#x5982;&#x679C;&#x672A;&#x8D85;&#x8FC7;&#x5F53;&#x65F6;&#x7684;&#x5BB9;&#x91CF;&#xFF0C;&#x5219;&#x8FD8;&#x6709;&#x5269;&#x4F59;&#x7A7A;&#x95F4;&#xFF0C;&#x90A3;&#x4E48;&#x76F4;&#x63A5;&#x6DFB;&#x52A0;&#x5230;&#x6700;&#x540E;&#xFF08;&#x63D2;&#x5165;&#x6307;&#x5B9A;&#x4F4D;&#x7F6E;&#xFF09;&#xFF0C;&#x7136;&#x540E;&#x8C03;&#x6574;&#x8FED;&#x4EE3;&#x5668;&#x3002;</li>
<li>&#x5982;&#x679C;&#x6CA1;&#x6709;&#x5269;&#x4F59;&#x7A7A;&#x95F4;&#x4E86;&#xFF0C;&#x5219;&#x4F1A;&#x91CD;&#x65B0;&#x914D;&#x7F6E;&#x7ED9;&#x5176;&#x539F;&#x6709;&#x5143;&#x7D20;&#x4E2A;&#x6570;&#x7684;&#x4E24;&#x500D;&#x7A7A;&#x95F4;&#xFF0C;&#x7136;&#x540E;&#x5C06;&#x539F;&#x7A7A;&#x95F4;&#x5143;&#x7D20;&#x901A;&#x8FC7;&#x590D;&#x5236;&#x7684;&#x65B9;&#x5F0F;&#x521D;&#x59CB;&#x5316;&#x65B0;&#x7A7A;&#x95F4;&#xFF0C;&#x518D;&#x5411;&#x65B0;&#x7A7A;&#x95F4;&#x589E;&#x52A0;&#x5143;&#x7D20;&#xFF0C;&#x6700;&#x540E;&#x6790;&#x6784;&#x5E76;&#x91CA;&#x653E;&#x539F;&#x7A7A;&#x95F4;&#xFF0C;&#x4E4B;&#x524D;&#x7684;&#x8FED;&#x4EE3;&#x5668;&#x4F1A;&#x5931;&#x6548;&#x3002;</li>
</ul>
</li>
<li>&#x6027;&#x80FD;&#xFF1A;<ul>
<li>&#x968F;&#x673A;&#x5B58;&#x53D6;&#x8BBF;&#x95EE;&#xFF0C;$O(1)$</li>
<li>&#x63D2;&#x5165;&#xFF1A;<ul>
<li>&#x5728;&#x6700;&#x540E;&#x63D2;&#x5165;&#xFF08;&#x7A7A;&#x95F4;&#x591F;&#xFF09;&#xFF1A;$O(1)$</li>
<li>&#x5728;&#x6700;&#x540E;&#x63D2;&#x5165;&#xFF08;&#x7A7A;&#x95F4;&#x4E0D;&#x591F;&#xFF09;&#xFF1A;&#x9700;&#x8981;&#x5185;&#x5B58;&#x7533;&#x8BF7;&#x548C;&#x91CA;&#x653E;&#xFF0C;&#x4EE5;&#x53CA;&#x5BF9;&#x4E4B;&#x524D;&#x6570;&#x636E;&#x8FDB;&#x884C;&#x62F7;&#x8D1D;</li>
<li>&#x5728;&#x4E2D;&#x95F4;&#x548C;&#x5934;&#x90E8;&#x63D2;&#x5165;&#xFF08;&#x7A7A;&#x95F4;&#x591F;&#xFF09;&#xFF1A;&#x5185;&#x5B58;&#x62F7;&#x8D1D;&#xFF0C;&#x9700;&#x8981;&#x632A;&#x52A8;&#x5927;&#x91CF;&#x7684;&#x6570;&#x636E;&#xFF0C;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A;$o(n)$</li>
</ul>
</li>
<li>&#x5220;&#x9664;&#xFF1A;<ul>
<li>&#x672B;&#x5C3E;&#x5220;&#x9664;&#xFF1A;$O(1)$</li>
<li>&#x4E2D;&#x95F4;&#x5220;&#x9664;&#xFF1A;&#x5185;&#x5B58;&#x62F7;&#x8D1D;&#xFF0C;$O(n)$</li>
</ul>
</li>
</ul>
</li>
<li>&#x9002;&#x7528;&#x573A;&#x666F;&#xFF1A;&#x7ECF;&#x5E38;&#x968F;&#x673A;&#x8BBF;&#x95EE;&#xFF0C;&#x4E14;&#x4E0D;&#x7ECF;&#x5E38;&#x5BF9;&#x975E;&#x5C3E;&#x7ED3;&#x70B9;&#x8FDB;&#x884C;&#x63D2;&#x5165;&#x5220;&#x9664;</li>
</ul>
<h4 id="list">list</h4>
<ul>
<li>&#x52A8;&#x6001;&#x94FE;&#x8868;&#xFF0C;&#x5728;&#x5806;&#x4E0A;&#x5206;&#x914D;&#x7A7A;&#x95F4;&#xFF0C;&#x6CA1;&#x63D2;&#x5165;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x90FD;&#x4F1A;&#x5206;&#x914D;&#x76F8;&#x5E94;&#x7A7A;&#x95F4;&#xFF0C;&#x6BCF;&#x5220;&#x9664;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x90FD;&#x4F1A;&#x91CA;&#x653E;&#x76F8;&#x5E94;&#x7A7A;&#x95F4;&#x3002;</li>
<li>&#x5E95;&#x5C42;&#x5B9E;&#x73B0;&#xFF1A;&#x53CC;&#x5411;&#x94FE;&#x8868;</li>
<li>&#x6027;&#x80FD;&#xFF1A;<ul>
<li>&#x8BBF;&#x95EE;&#xFF1A;$O(n)$</li>
<li>&#x63D2;&#x5165;&#xFF1A;$O(1)$</li>
<li>&#x5220;&#x9664;&#xFF1A;$O(1)$</li>
</ul>
</li>
<li>&#x9002;&#x7528;&#x573A;&#x666F;&#xFF1A;&#x7ECF;&#x5E38;&#x63D2;&#x5165;&#x5220;&#x9664;&#x5927;&#x91CF;&#x6570;&#x636E;</li>
</ul>
<h4 id="vector-&#x548C;-list-&#x533A;&#x522B;">vector &#x548C; list &#x533A;&#x522B;</h4>
<ul>
<li><p>vector&#x5E95;&#x5C42;&#x662F;&#x73B0;&#x5B9E;&#x6570;&#x7EC4;&#xFF0C;list&#x5E95;&#x5C42;&#x5B9E;&#x73B0;&#x662F;&#x53CC;&#x5411;&#x94FE;&#x8868;</p>
</li>
<li><p>vector&#x652F;&#x6301;&#x968F;&#x673A;&#x8BBF;&#x95EE;&#x6027;&#x80FD;&#x597D;&#xFF0C;&#x63D2;&#x5165;&#x5220;&#x9664;&#x6027;&#x80FD;&#x5DEE;&#xFF1B;list&#x4E0D;&#x652F;&#x6301;&#x968F;&#x673A;&#x8BBF;&#x95EE;&#xFF0C;&#x4F46;&#x63D2;&#x5165;&#x5220;&#x9664;&#x6027;&#x80FD;&#x597D;&#x3002; </p>
</li>
<li><p>vector&#x662F;&#x987A;&#x5E8F;&#x5B58;&#x50A8;&#xFF0C;list&#x4E0D;&#x662F;</p>
</li>
<li><p>vector&#x5728;&#x975E;&#x5C3E;&#x8282;&#x70B9;&#x8FDB;&#x884C;&#x63D2;&#x5165;&#x5220;&#x9664;&#x4F1A;&#x5BFC;&#x81F4;&#x5185;&#x5B58;&#x62F7;&#x8D1D;&#xFF0C;list&#x4E0D;&#x4F1A;</p>
</li>
<li><p>vector&#x662F;&#x4E00;&#x6B21;&#x6027;&#x5206;&#x914D;&#x597D;&#x5185;&#x5B58;&#xFF0C;&#x4E0D;&#x591F;&#x65F6;&#x8FDB;&#x884C;2&#x500D;&#x6269;&#x5BB9;&#xFF0C;list&#x6BCF;&#x6B21;&#x63D2;&#x5165;&#x65B0;&#x7ED3;&#x70B9;&#x90FD;&#x4F1A;&#x8FDB;&#x884C;&#x5185;&#x5B58;&#x7533;&#x8BF7;&#x3002;</p>
</li>
</ul>
<h3 id="12---&#x4EC0;&#x4E48;&#x60C5;&#x51B5;&#x4E0B;&#x7528;vector&#x3001;list&#x3001;deque&#xFF1F;">12 - &#x4EC0;&#x4E48;&#x60C5;&#x51B5;&#x4E0B;&#x7528;vector&#x3001;list&#x3001;deque&#xFF1F;</h3>
<ul>
<li><p>vector&#x53EF;&#x4EE5;&#x968F;&#x673A;&#x5B58;&#x50A8;&#x5143;&#x7D20;&#xFF08;&#x5373;&#x53EF;&#x4EE5;&#x901A;&#x8FC7;&#x516C;&#x5F0F;&#x76F4;&#x63A5;&#x8BA1;&#x7B97;&#x51FA;&#x5143;&#x7D20;&#x5730;&#x5740;&#xFF0C;&#x4E0D;&#x9700;&#x8981;&#x6328;&#x4E2A;&#x67E5;&#x627E;&#xFF09;&#xFF0C;&#x4F46;&#x5728;&#x975E;&#x5C3E;&#x90E8;&#x63D2;&#x5165;&#x5220;&#x9664;&#x6570;&#x636E;&#x65F6;&#xFF0C;&#x6548;&#x7387;&#x5F88;&#x4F4E;&#xFF0C;&#x9002;&#x5408;&#x5BF9;&#x8C61;&#x7B80;&#x5355;&#xFF0C;&#x5BF9;&#x8C61;&#x6570;&#x636E;&#x91CF;&#x53D8;&#x5316;&#x4E0D;&#x5927;&#xFF0C;&#x968F;&#x673A;&#x8BBF;&#x95EE;&#x9891;&#x7E41;&#x3002;&#x9664;&#x975E;&#x7279;&#x6B8A;&#x60C5;&#x51B5;&#xFF0C;&#x5C3D;&#x53EF;&#x80FD;&#x7684;&#x4F7F;&#x7528;vector&#x800C;&#x975E;deque&#xFF0C;&#x56E0;&#x4E3A;deque&#x7684;&#x8FED;&#x4EE3;&#x5668;&#x6BD4;vector&#x590D;&#x6742;&#x5F88;&#x591A;&#x3002;</p>
</li>
<li><p>list&#x4E0D;&#x652F;&#x6301;&#x968F;&#x673A;&#x5B58;&#x50A8;&#xFF0C;&#x9002;&#x7528;&#x4E8E;&#x5BF9;&#x8C61;&#x5927;&#x3001;&#x5BF9;&#x8C61;&#x6570;&#x91CF;&#x53D8;&#x5316;&#x9891;&#x7E41;&#xFF0C;&#x63D2;&#x5165;&#x548C;&#x4EA7;&#x51FA;&#x9891;&#x7E41;&#xFF0C;&#x5199;&#x591A;&#x8BFB;&#x5C11;&#x7684;&#x60C5;&#x666F;</p>
</li>
<li><p>&#x9700;&#x8981;&#x4ECE;&#x9996;&#x5C3E;&#x4E24;&#x7AEF;&#x8FDB;&#x884C;&#x63D2;&#x5165;&#x6216;&#x5220;&#x9664;&#x64CD;&#x4F5C;&#x7684;&#x65F6;&#x5019;&#x7528;deque</p>
</li>
</ul>
<h3 id="13---map-&#x548C;-set-&#x7684;&#x533A;&#x522B;&#xFF1F;&#x4E3A;&#x4F55;&#x4F7F;&#x7528;&#x7EA2;&#x9ED1;&#x6811;&#x5B9E;&#x73B0;&#xFF1F;">13 - map &#x548C; set &#x7684;&#x533A;&#x522B;&#xFF1F;&#x4E3A;&#x4F55;&#x4F7F;&#x7528;&#x7EA2;&#x9ED1;&#x6811;&#x5B9E;&#x73B0;&#xFF1F;</h3>
<p>map&#x548C;set&#x90FD;&#x662F;C++&#x7684;&#x5173;&#x8054;&#x5BB9;&#x5668;&#xFF0C;&#x5E95;&#x5C42;&#x5B9E;&#x73B0;&#x90FD;&#x662F;&#x7EA2;&#x9ED1;&#x6811;&#xFF08;RB-Tree&#xFF09;&#x3002;&#x7531;&#x4E8E;map&#x548C;set&#x5F00;&#x653E;&#x5404;&#x79CD;&#x501F;&#x53E3;&#x64CD;&#x4F5C;&#xFF0C;RB-Tree&#x4E5F;&#x90FD;&#x63D0;&#x4F9B;&#xFF0C;&#x6240;&#x4EE5;&#x51E0;&#x4E4E;&#x6240;&#x6709;&#x7684;map&#x548C;set&#x7684;&#x64CD;&#x4F5C;&#x884C;&#x4E3A;&#xFF0C;&#x90FD;&#x53EA;&#x662F;&#x8F6C;&#x8C03;RB-Tree&#x7684;&#x64CD;&#x4F5C;&#x884C;&#x4E3A;&#x3002;</p>
<h4 id="131---map-&#x548C;-set-&#x7684;&#x533A;&#x522B;&#xFF1A;">13.1 - map &#x548C; set &#x7684;&#x533A;&#x522B;&#xFF1A;</h4>
<ul>
<li>map&#x4E2D;&#x7684;&#x5143;&#x7D20;&#x662F; key - value &#x952E;&#x503C;&#x5BF9;&#xFF1B;Set&#x5219;&#x53EA;&#x662F;&#x5173;&#x952E;&#x5B57;&#x7684;&#x7B80;&#x5355;&#x96C6;&#x5408;&#xFF0C;set&#x4E2D;&#x6BCF;&#x4E2A;&#x5143;&#x7D20;&#x7684;&#x503C;&#x90FD;&#x552F;&#x4E00;&#x3002;</li>
<li>set&#x7684;&#x8FED;&#x4EE3;&#x5668;&#x662F;const&#x7684;&#xFF0C;&#x4E0D;&#x5141;&#x8BB8;&#x4FEE;&#x6539;&#x5143;&#x7D20;&#x7684;&#x503C;&#xFF0C;&#x800C;map&#x5141;&#x8BB8;&#x4FEE;&#x6539;value&#xFF0C;&#x4F46;&#x4E0D;&#x5141;&#x8BB8;&#x4FEE;&#x6539;key&#x3002;<ul>
<li>&#x539F;&#x56E0;&#x662F;&#x56E0;&#x4E3A;map&#x548C;set&#x662F;&#x6839;&#x636E;&#x5173;&#x952E;&#x5B57;&#x6392;&#x5E8F;&#x6765;&#x4FDD;&#x8BC1;&#x5176;&#x6709;&#x5E8F;&#x6027;&#x7684;&#x3002;&#x5982;&#x679C;&#x5141;&#x8BB8;&#x4FEE;&#x6539;key &#x7684;&#x8BDD;&#xFF0C;&#x90A3;&#x4E48;&#x9996;&#x5148;&#x9700;&#x8981;&#x5220;&#x9664;&#x8BE5;&#x952E;&#xFF0C;&#x7136;&#x540E;&#x8C03;&#x8282;&#x5E73;&#x8861;&#xFF0C;&#x518D;&#x63D2;&#x5165;&#x4FEE;&#x6539;&#x540E;&#x7684;&#x952E;&#x503C;&#xFF0C;&#x8C03;&#x8282;&#x5E73;&#x8861;&#xFF0C;&#x5982;&#x6B64;&#x4E00;&#x6765;&#xFF0C;&#x4E25;&#x91CD;&#x7834;&#x574F;&#x4E86;map &#x548C;set &#x7684;&#x7ED3;&#x6784;&#xFF0C;&#x5BFC;&#x81F4;iterator &#x5931;&#x6548;&#xFF0C;&#x4E0D;&#x77E5;&#x9053;&#x5E94;&#x8BE5;&#x6307;&#x5411;&#x6539;&#x53D8;&#x524D;&#x7684;&#x4F4D;&#x7F6E;&#xFF0C;&#x8FD8;&#x662F;&#x6307;&#x5411;&#x6539;&#x53D8;&#x540E;&#x7684;&#x4F4D;&#x7F6E;&#x3002;&#x6240;&#x4EE5;STL &#x4E2D;&#x5C06;set &#x7684;&#x8FED;&#x4EE3;&#x5668;&#x8BBE;&#x7F6E;&#x6210;const&#xFF0C;&#x4E0D;&#x5141;&#x8BB8;&#x4FEE;&#x6539;&#x8FED;&#x4EE3;&#x5668;&#x7684;&#x503C;&#xFF1B;&#x800C;map &#x7684;&#x8FED;&#x4EE3;&#x5668;&#x5219;&#x4E0D;&#x5141;&#x8BB8;&#x4FEE;&#x6539;key &#x503C;&#xFF0C;&#x5141;&#x8BB8;&#x4FEE;&#x6539;value &#x503C;&#x3002;</li>
</ul>
</li>
<li>map &#x652F;&#x6301;&#x4E0B;&#x6807;&#x64CD;&#x4F5C;&#xFF0C;set &#x4E0D;&#x652F;&#x6301;&#x4E0B;&#x6807;&#x64CD;&#x4F5C;&#x3002;map &#x53EF;&#x4EE5;&#x7528;key &#x505A;&#x4E0B;&#x6807;&#xFF0C;map &#x7684;&#x4E0B;&#x6807;&#x8FD0;&#x7B97;&#x7B26;[ ]&#x5C06;&#x5173;&#x952E;&#x7801;&#x4F5C;&#x4E3A;&#x4E0B;&#x6807;&#x53BB;&#x6267;&#x884C;&#x67E5;&#x627E;&#xFF0C;&#x5982;&#x679C;&#x5173;&#x952E;&#x7801;&#x4E0D;&#x5B58;&#x5728;&#xFF0C;&#x5219;&#x63D2;&#x5165;&#x4E00;&#x4E2A;&#x5177;&#x6709;&#x8BE5;&#x5173;&#x952E;&#x7801;&#x548C;mapped_type&#x7C7B;&#x578B;&#x9ED8;&#x8BA4;&#x503C;&#x7684;&#x5143;&#x7D20;&#x81F3;map &#x4E2D;&#x3002;<ul>
<li>&#x56E0;&#x6B64;&#x4E0B;&#x6807;&#x8FD0;&#x7B97;&#x7B26;[ ]&#x5728;map &#x5E94;&#x7528;&#x4E2D;&#x9700;&#x8981;&#x614E;&#x7528;&#xFF0C;const_map &#x4E0D;&#x80FD;&#x7528;&#xFF0C;&#x53EA;&#x5E0C;&#x671B;&#x786E;&#x5B9A;&#x67D0;&#x4E00;&#x4E2A;&#x5173;&#x952E;&#x503C;&#x662F;&#x5426;&#x5B58;&#x5728;&#x800C;&#x4E0D;&#x5E0C;&#x671B;&#x63D2;&#x5165;&#x5143;&#x7D20;&#x65F6;&#x4E5F;&#x4E0D;&#x5E94;&#x8BE5;&#x4F7F;&#x7528;&#xFF0C;mapped_type &#x7C7B;&#x578B;&#x6CA1;&#x6709;&#x9ED8;&#x8BA4;&#x503C;&#x4E5F;&#x4E0D;&#x5E94;&#x8BE5;&#x4F7F;&#x7528;&#x3002;&#x5982;&#x679C;find &#x80FD;&#x89E3;&#x51B3;&#x9700;&#x8981;&#xFF0C;&#x5C3D;&#x53EF;&#x80FD;&#x7528;find&#x3002;</li>
</ul>
</li>
</ul>
<h4 id="132---&#x7EA2;&#x9ED1;&#x6811;&#x662F;&#x600E;&#x4E48;&#x80FD;&#x591F;&#x540C;&#x65F6;&#x5B9E;&#x73B0;&#x8FD9;&#x4E24;&#x79CD;&#x5BB9;&#x5668;&#xFF1F;-&#x4E3A;&#x4EC0;&#x4E48;&#x4F7F;&#x7528;&#x7EA2;&#x9ED1;&#x6811;&#xFF1F;">13.2 - &#x7EA2;&#x9ED1;&#x6811;&#x662F;&#x600E;&#x4E48;&#x80FD;&#x591F;&#x540C;&#x65F6;&#x5B9E;&#x73B0;&#x8FD9;&#x4E24;&#x79CD;&#x5BB9;&#x5668;&#xFF1F; &#x4E3A;&#x4EC0;&#x4E48;&#x4F7F;&#x7528;&#x7EA2;&#x9ED1;&#x6811;&#xFF1F;</h4>
<ul>
<li>&#x4ED6;&#x4EEC;&#x7684;&#x5E95;&#x5C42;&#x90FD;&#x662F;&#x4EE5;&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x7ED3;&#x6784;&#x5B9E;&#x73B0;&#xFF0C;&#x56E0;&#x6B64;&#x63D2;&#x5165;&#x5220;&#x9664;&#x7B49;&#x64CD;&#x4F5C;&#x90FD;&#x5728;O(logn)&#x65F6;&#x95F4;&#x5185;&#x5B8C;&#x6210;&#xFF0C;&#x56E0;&#x6B64;&#x53EF;&#x4EE5;&#x5B8C;&#x6210;&#x9AD8;&#x6548;&#x7684;&#x63D2;&#x5165;&#x5220;&#x9664;&#xFF1B;</li>
<li>&#x5728;&#x8FD9;&#x91CC;&#x5B9A;&#x4E49;&#x4E86;&#x4E00;&#x4E2A;&#x6A21;&#x7248;&#x53C2;&#x6570;&#xFF0C;&#x5982;&#x679C;&#x5B83;&#x662F;key&#x90A3;&#x4E48;&#x5B83;&#x5C31;&#x662F;set&#xFF0C;&#x5982;&#x679C;&#x5B83;&#x662F;map&#xFF0C;&#x90A3;&#x4E48;&#x5B83;&#x5C31;&#x662F;map&#xFF1B;&#x5E95;&#x5C42;&#x662F;&#x7EA2;&#x9ED1;&#x6811;&#xFF0C;&#x5B9E;&#x73B0;map&#x7684;&#x7EA2;&#x9ED1;&#x6811;&#x7684;&#x8282;&#x70B9;&#x6570;&#x636E;&#x7C7B;&#x578B;&#x662F;key+value&#xFF0C;&#x800C;&#x5B9E;&#x73B0;set&#x7684;&#x8282;&#x70B9;&#x6570;&#x636E;&#x7C7B;&#x578B;&#x662F;value</li>
<li>&#x56E0;&#x4E3A;map&#x548C;set&#x8981;&#x6C42;&#x662F;&#x81EA;&#x52A8;&#x6392;&#x5E8F;&#x7684;&#xFF0C;&#x7EA2;&#x9ED1;&#x6811;&#x80FD;&#x591F;&#x5B9E;&#x73B0;&#x8FD9;&#x4E00;&#x529F;&#x80FD;&#xFF0C;&#x800C;&#x4E14;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x6BD4;&#x8F83;&#x4F4E;&#x3002;</li>
</ul>
<h4 id="133---&#x9002;&#x7528;&#x573A;&#x666F;&#xFF1A;">13.3 - &#x9002;&#x7528;&#x573A;&#x666F;&#xFF1A;</h4>
<ul>
<li>map&#xFF1A;&#x6709;&#x5E8F;&#x952E;&#x503C;&#x5BF9;&#x4E0D;&#x91CD;&#x590D;&#x6620;&#x5C04;</li>
<li>set&#xFF1A;&#x6709;&#x5E8F;&#x4E0D;&#x91CD;&#x590D;&#x96C6;&#x5408;</li>
</ul>
<h3 id="14---map-&#x548C;-unorderedmap&#x5E95;&#x5C42;&#x5B58;&#x653E;&#x5F62;&#x5F0F;">14 - map &#x548C; unordered_map&#x5E95;&#x5C42;&#x5B58;&#x653E;&#x5F62;&#x5F0F;</h3>
<ul>
<li>map&#xFF1A;&#x7EA2;&#x9ED1;&#x6811;</li>
<li>unordered_map&#xFF1A;&#x54C8;&#x5E0C;&#x8868;</li>
</ul>
<h3 id="15---map&#x63D2;&#x5165;&#x65B9;&#x5F0F;&#x6709;&#x54EA;&#x51E0;&#x79CD;&#xFF1F;">15 - map&#x63D2;&#x5165;&#x65B9;&#x5F0F;&#x6709;&#x54EA;&#x51E0;&#x79CD;&#xFF1F;</h3>
<ol>
<li>&#x7528;insert&#x51FD;&#x6570;&#x63D2;&#x5165;pair&#x6570;&#x636E;</li>
</ol>
<pre><code class="lang-cpp">mapStudent.insert(pair&lt;<span class="hljs-keyword">int</span>, <span class="hljs-built_in">string</span>&gt;(<span class="hljs-number">1</span>,<span class="hljs-string">&quot;student_one&quot;</span>));;
</code></pre>
<ol>
<li>&#x7528;insert&#x51FD;&#x6570;&#x63D2;&#x5165;value_type&#x6570;&#x636E;</li>
</ol>
<pre><code class="lang-cpp">mapStudent.insert(<span class="hljs-built_in">map</span>&lt;<span class="hljs-keyword">int</span>,<span class="hljs-built_in">string</span>&gt;::value_type(<span class="hljs-number">1</span>,<span class="hljs-string">&quot;student_one&quot;</span>));
</code></pre>
<ol>
<li>&#x5728;insert&#x51FD;&#x6570;&#x4E2D;&#x4F7F;&#x7528;make_pair()&#x51FD;&#x6570;</li>
</ol>
<pre><code class="lang-cpp">mapStudent.insert(make_pair(<span class="hljs-number">1</span>,<span class="hljs-string">&quot;student_one&quot;</span>));
</code></pre>
<ol>
<li>&#x7528;&#x6570;&#x7EC4;&#x65B9;&#x5F0F;&#x63D2;&#x5165;</li>
</ol>
<pre><code class="lang-cpp">mapStudent[<span class="hljs-number">1</span>] = <span class="hljs-string">&quot;student_one&quot;</span>;
</code></pre>
<h3 id="16---map&#x4E2D;&#x548C;find&#x7684;&#x533A;&#x522B;&#x662F;&#x4EC0;&#x4E48;&#xFF1F;">16 - map&#x4E2D;[]&#x548C;find&#x7684;&#x533A;&#x522B;&#x662F;&#x4EC0;&#x4E48;&#xFF1F;</h3>
<ul>
<li>map&#x7684;&#x4E0B;&#x6807;&#x8FD0;&#x7B97;[]&#x7684;&#x4F5C;&#x7528;&#x662F;&#xFF1A;&#x5C06;key&#x4F5C;&#x4E3A;&#x4E0B;&#x6807;&#x53BB;&#x6267;&#x884C;&#x67E5;&#x627E;&#xFF0C;&#x5E76;&#x8FD4;&#x56DE;&#x76F8;&#x5E94;&#x7684;&#x503C;&#xFF1B;&#x5982;&#x679C;&#x4E0D;&#x5B58;&#x5728;&#x8FD9;&#x4E2A;key&#xFF0C;&#x5C31;&#x5C06;&#x4E00;&#x4E2A;&#x5177;&#x6709;&#x8BE5;key&#x548C;value&#x7684;&#x952E;&#x503C;&#x5BF9;&#x63D2;&#x5165;map</li>
<li>find&#x51FD;&#x6570;&#x662F;&#x7528;&#x5173;&#x952E;&#x5B57;&#x6267;&#x884C;&#x67E5;&#x627E;&#xFF0C;&#x627E;&#x5230;&#x4E86;&#x8FD4;&#x56DE;&#x8BE5;&#x4F4D;&#x7F6E;&#x7684;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x5982;&#x679C;&#x4E0D;&#x5B58;&#x5728;&#x8FD4;&#x56DE;&#x5C3E;&#x8FED;&#x4EE3;&#x5668;</li>
</ul>
<h3 id="17---vector&#x8D8A;&#x754C;&#x8BBF;&#x95EE;&#x4E0B;&#x6807;&#xFF0C;map&#x8D8A;&#x754C;&#x8BBF;&#x95EE;&#x4E0B;&#x6807;&#xFF1F;vector&#x5220;&#x9664;&#x5143;&#x7D20;&#x65F6;&#x4F1A;&#x4E0D;&#x4F1A;&#x91CA;&#x653E;&#x7A7A;&#x95F4;&#xFF1F;">17 - vector&#x8D8A;&#x754C;&#x8BBF;&#x95EE;&#x4E0B;&#x6807;&#xFF0C;map&#x8D8A;&#x754C;&#x8BBF;&#x95EE;&#x4E0B;&#x6807;&#xFF1F;vector&#x5220;&#x9664;&#x5143;&#x7D20;&#x65F6;&#x4F1A;&#x4E0D;&#x4F1A;&#x91CA;&#x653E;&#x7A7A;&#x95F4;&#xFF1F;</h3>
<ol>
<li><p>&#x901A;&#x8FC7;&#x4E0B;&#x6807;&#x8BBF;&#x95EE;vector&#x4E2D;&#x7684;&#x5143;&#x7D20;&#x4F1A;&#x505A;&#x8FB9;&#x754C;&#x68C0;&#x67E5;&#xFF0C;&#x4F46;&#x8BE5;&#x5904;&#x7684;&#x5B9E;&#x73B0;&#x65B9;&#x5F0F;&#x8981;&#x770B;&#x5177;&#x4F53;&#x7684;IDE&#xFF0C;&#x4E0D;&#x540C;IDE&#x7684;&#x5B9E;&#x73B0;&#x65B9;&#x5F0F;&#x4E0D;&#x4E00;&#x6837;&#xFF0C;&#x786E;&#x4FDD;&#x4E0D;&#x53EF;&#x8BBF;&#x95EE;&#x8D8A;&#x754C;&#x5730;&#x5740;</p>
</li>
<li><p>map&#x7684;&#x4E0B;&#x6807;&#x8FD0;&#x7B97;[]&#x7684;&#x4F5C;&#x7528;&#x662F;&#xFF1A;&#x5C06;key&#x4F5C;&#x4E3A;&#x4E0B;&#x6807;&#x53BB;&#x6267;&#x884C;&#x67E5;&#x627E;&#xFF0C;&#x5E76;&#x8FD4;&#x56DE;&#x76F8;&#x5E94;&#x7684;&#x503C;&#xFF1B;&#x5982;&#x679C;&#x4E0D;&#x5B58;&#x5728;&#x8FD9;&#x4E2A;key&#xFF0C;&#x5C31;&#x5C06;&#x4E00;&#x4E2A;&#x5177;&#x6709;&#x8BE5;key&#x548C;value&#x7684;&#x952E;&#x503C;&#x5BF9;&#x63D2;&#x5165;map</p>
</li>
</ol>
<p>erase&#x51FD;&#x6570;&#x53EA;&#x80FD;&#x5220;&#x9664;&#x5185;&#x5BB9;&#xFF0C;&#x4E0D;&#x80FD;&#x6539;&#x53D8;vector&#x5BB9;&#x91CF;&#x7684;&#x5927;&#x5C0F;&#xFF0C;&#x5B83;&#x5220;&#x9664;&#x4E86;it&#x8FED;&#x4EE3;&#x5668;&#x6307;&#x5411;&#x7684;&#x5143;&#x7D20;&#xFF0C;&#x5E76;&#x4E14;&#x8FD4;&#x56DE;&#x88AB;&#x5220;&#x9664;&#x7684;it&#x4E4B;&#x540E;&#x7684;&#x4E0B;&#x4E00;&#x4E2A;&#x8FED;&#x4EE3;&#x5668;</p>
<p>clear&#x51FD;&#x6570;&#x53EA;&#x80FD;&#x6E05;&#x7A7A;&#x5185;&#x5BB9;&#xFF0C;&#x4E5F;&#x4E0D;&#x80FD;&#x6539;&#x53D8;capacity&#x5BB9;&#x91CF;&#x5927;&#x5C0F;&#xFF1B;</p>
<p>&#x5982;&#x679C;&#x60F3;&#x8981;&#x5728;&#x5220;&#x9664;&#x5185;&#x5BB9;&#x7684;&#x65F6;&#x5019;&#x540C;&#x65F6;&#x91CA;&#x653E;&#x5185;&#x5B58;&#xFF0C;&#x53EF;&#x4EE5;&#x9009;&#x7528;deque&#x5BB9;&#x5668;</p>
<h3 id="18---&#x4F7F;&#x7528;&#x6709;&#x5E8F;&#x5BB9;&#x5668;&#x63D2;&#x5165;&#x81EA;&#x5B9A;&#x4E49;&#x5BF9;&#x8C61;&#x8981;&#x600E;&#x4E48;&#x505A;&#xFF1F;">18 - &#x4F7F;&#x7528;&#x6709;&#x5E8F;&#x5BB9;&#x5668;&#x63D2;&#x5165;&#x81EA;&#x5B9A;&#x4E49;&#x5BF9;&#x8C61;&#x8981;&#x600E;&#x4E48;&#x505A;&#xFF1F;</h3>
<p>&#x6807;&#x51C6;&#x5E93;&#x91CC;&#x4E00;&#x5171;&#x6709;&#x56DB;&#x79CD;&#x6709;&#x5E8F;&#x5BB9;&#x5668;&#xFF1A;set/multiset &#x548C; map/multimap&#x3002;set &#x662F;&#x96C6;&#x5408;&#xFF0C;map &#x662F;&#x5173;&#x8054;&#x6570;&#x7EC4;&#xFF08;&#x5728;&#x5176;&#x4ED6;&#x8BED;&#x8A00;&#x91CC;&#x4E5F;&#x53EB;&#x201C;&#x5B57;&#x5178;&#x201D;&#xFF09;&#x3002;</p>
<p>&#x56E0;&#x4E3A;&#x6709;&#x5E8F;&#x5BB9;&#x5668;&#x7684;&#x6570;&#x91CF;&#x5F88;&#x5C11;&#xFF0C;&#x6240;&#x4EE5;&#x4F7F;&#x7528;&#x7684;&#x5173;&#x952E;&#x5C31;&#x662F;&#x8981;&#x7406;&#x89E3;&#x5B83;&#x7684;&#x201C;&#x6709;&#x5E8F;&#x201D;&#x6982;&#x5FF5;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;&#x8BF4;&#xFF0C;<strong>&#x5BB9;&#x5668;&#x662F;&#x5982;&#x4F55;&#x5224;&#x65AD;&#x4E24;&#x4E2A;&#x5143;&#x7D20;&#x7684;&#x201C;&#x5148;&#x540E;&#x6B21;&#x5E8F;&#x201D;&#xFF0C;&#x77E5;&#x9053;&#x4E86;&#x8FD9;&#x4E00;&#x70B9;&#xFF0C;&#x624D;&#x80FD;&#x6B63;&#x786E;&#x5730;&#x6392;&#x5E8F;&#x3002;</strong></p>
<p>&#x8FD9;&#x5C31;&#x5BFC;&#x81F4;&#x4E86;&#x6709;&#x5E8F;&#x5BB9;&#x5668;&#x4E0E;&#x987A;&#x5E8F;&#x5BB9;&#x5668;&#x7684;&#x53E6;&#x4E00;&#x4E2A;&#x6839;&#x672C;&#x533A;&#x522B;&#xFF0C;&#x5728;&#x5B9A;&#x4E49;&#x5BB9;&#x5668;&#x7684;&#x65F6;&#x5019;&#x5FC5;&#x987B;&#x8981;&#x6307;&#x5B9A; key &#x7684;&#x6BD4;&#x8F83;&#x51FD;&#x6570;&#x3002;&#x53EA;&#x4E0D;&#x8FC7;&#x8FD9;&#x4E2A;&#x51FD;&#x6570;&#x901A;&#x5E38;&#x662F;&#x9ED8;&#x8BA4;&#x7684; less&#xFF0C;&#x8868;&#x793A;&#x5C0F;&#x4E8E;&#x5173;&#x7CFB;&#xFF0C;&#x4E0D;&#x7528;&#x7279;&#x610F;&#x5199;&#x51FA;&#x6765;&#xFF1A;</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">template</span>&lt;
    <span class="hljs-keyword">class</span> T                          <span class="hljs-comment">// &#x6A21;&#x677F;&#x53C2;&#x6570;&#x53EA;&#x6709;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x7C7B;&#x578B;</span>
&gt; <span class="hljs-keyword">class</span> <span class="hljs-built_in">vector</span>;                      <span class="hljs-comment">// vector</span>

<span class="hljs-keyword">template</span>&lt;
    <span class="hljs-keyword">class</span> Key,                      <span class="hljs-comment">// &#x6A21;&#x677F;&#x53C2;&#x6570;&#x662F;key&#x7C7B;&#x578B;&#xFF0C;&#x5373;&#x5143;&#x7D20;&#x7C7B;&#x578B;</span>
    <span class="hljs-keyword">class</span> Compare = <span class="hljs-built_in">std</span>::less&lt;Key&gt;  <span class="hljs-comment">// &#x6BD4;&#x8F83;&#x51FD;&#x6570;</span>
&gt; <span class="hljs-keyword">class</span> <span class="hljs-built_in">set</span>;                        <span class="hljs-comment">// &#x96C6;&#x5408;</span>

<span class="hljs-keyword">template</span>&lt;
    <span class="hljs-keyword">class</span> Key,                      <span class="hljs-comment">// &#x7B2C;&#x4E00;&#x4E2A;&#x6A21;&#x677F;&#x53C2;&#x6570;&#x662F;key&#x7C7B;&#x578B;</span>
    <span class="hljs-keyword">class</span> T,                        <span class="hljs-comment">// &#x7B2C;&#x4E8C;&#x4E2A;&#x6A21;&#x677F;&#x53C2;&#x6570;&#x662F;&#x5143;&#x7D20;&#x7C7B;&#x578B;</span>
    <span class="hljs-keyword">class</span> Compare = <span class="hljs-built_in">std</span>::less&lt;Key&gt;  <span class="hljs-comment">// &#x6BD4;&#x8F83;&#x51FD;&#x6570;</span>
&gt; <span class="hljs-keyword">class</span> <span class="hljs-built_in">map</span>;                        <span class="hljs-comment">// &#x5173;&#x8054;&#x6570;&#x7EC4;</span>
</code></pre>
<p>C++ &#x91CC;&#x7684; int&#x3001;string &#x7B49;&#x57FA;&#x672C;&#x7C7B;&#x578B;&#x90FD;&#x652F;&#x6301;&#x6BD4;&#x8F83;&#x6392;&#x5E8F;&#xFF0C;&#x653E;&#x8FDB;&#x6709;&#x5E8F;&#x5BB9;&#x5668;&#x91CC;&#x6BEB;&#x65E0;&#x95EE;&#x9898;&#x3002;&#x4F46;&#x5F88;&#x591A;&#x81EA;&#x5B9A;&#x4E49;&#x7C7B;&#x578B;&#x6CA1;&#x6709;&#x9ED8;&#x8BA4;&#x7684;&#x6BD4;&#x8F83;&#x51FD;&#x6570;&#xFF0C;&#x8981;&#x4F5C;&#x4E3A;&#x5BB9;&#x5668;&#x7684; key &#x5C31;&#x6709;&#x70B9;&#x9EBB;&#x70E6;&#x3002;</p>
<p><strong>&#x89E3;&#x51B3;&#x8FD9;&#x4E2A;&#x95EE;&#x9898;&#x6709;&#x4E24;&#x79CD;&#x529E;&#x6CD5;&#xFF1A;&#x4E00;&#x4E2A;&#x662F;&#x91CD;&#x8F7D;&#x201C;&lt;&#x201D;&#xFF0C;&#x53E6;&#x4E00;&#x4E2A;&#x662F;&#x81EA;&#x5B9A;&#x4E49;&#x6A21;&#x677F;&#x53C2;&#x6570;&#x3002;</strong></p>
<p>&#x6BD4;&#x5982;&#x8BF4;&#x6211;&#x4EEC;&#x6709;&#x4E00;&#x4E2A; Point &#x7C7B;&#xFF0C;&#x5B83;&#x662F;&#x6CA1;&#x6709;&#x5927;&#x5C0F;&#x6982;&#x5FF5;&#x7684;&#xFF0C;&#x4F46;&#x53EA;&#x8981;&#x7ED9;&#x5B83;&#x91CD;&#x8F7D;&#x201C;&lt;&#x201D;&#x64CD;&#x4F5C;&#x7B26;&#xFF0C;&#x5C31;&#x53EF;&#x4EE5;&#x653E;&#x8FDB;&#x6709;&#x5E8F;&#x5BB9;&#x5668;&#x91CC;&#x4E86;&#xFF1A;</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">bool</span> <span class="hljs-keyword">operator</span>&lt;(<span class="hljs-keyword">const</span> Point&amp; a, <span class="hljs-keyword">const</span> Point&amp; b)
{
    <span class="hljs-keyword">return</span> a.x &lt; b.x;            <span class="hljs-comment">// &#x81EA;&#x5B9A;&#x4E49;&#x6BD4;&#x8F83;&#x8FD0;&#x7B97;</span>
}

<span class="hljs-built_in">set</span>&lt;Point&gt; s;                    <span class="hljs-comment">// &#x73B0;&#x5728;&#x5C31;&#x53EF;&#x4EE5;&#x6B63;&#x786E;&#x5730;&#x653E;&#x5165;&#x6709;&#x5E8F;&#x5BB9;&#x5668;</span>
s.emplace(<span class="hljs-number">7</span>);
s.emplace(<span class="hljs-number">3</span>);
</code></pre>
<p>&#x53E6;&#x4E00;&#x79CD;&#x65B9;&#x5F0F;&#x662F;&#x7F16;&#x5199;&#x4E13;&#x95E8;&#x7684;&#x51FD;&#x6570;&#x5BF9;&#x8C61;&#x6216;&#x8005; lambda &#x8868;&#x8FBE;&#x5F0F;&#xFF0C;&#x7136;&#x540E;&#x5728;&#x5BB9;&#x5668;&#x7684;&#x6A21;&#x677F;&#x53C2;&#x6570;&#x91CC;&#x6307;&#x5B9A;&#x3002;&#x8FD9;&#x79CD;&#x65B9;&#x5F0F;&#x66F4;&#x7075;&#x6D3B;&#xFF0C;&#x800C;&#x4E14;&#x53EF;&#x4EE5;&#x5B9E;&#x73B0;&#x4EFB;&#x610F;&#x7684;&#x6392;&#x5E8F;&#x51C6;&#x5219;&#xFF1A;</p>
<pre><code class="lang-cpp"><span class="hljs-built_in">set</span>&lt;<span class="hljs-keyword">int</span>&gt; s = {<span class="hljs-number">7</span>, <span class="hljs-number">3</span>, <span class="hljs-number">9</span>};           <span class="hljs-comment">// &#x5B9A;&#x4E49;&#x96C6;&#x5408;&#x5E76;&#x521D;&#x59CB;&#x5316;3&#x4E2A;&#x5143;&#x7D20;</span>

<span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span>&amp; x : s) {                <span class="hljs-comment">// &#x8303;&#x56F4;&#x5FAA;&#x73AF;&#x8F93;&#x51FA;&#x5143;&#x7D20;</span>
    <span class="hljs-built_in">cout</span> &lt;&lt; x &lt;&lt; <span class="hljs-string">&quot;,&quot;</span>;              <span class="hljs-comment">// &#x4ECE;&#x5C0F;&#x5230;&#x5927;&#x6392;&#x5E8F;&#xFF0C;3,7,9</span>
}   

<span class="hljs-keyword">auto</span> comp = [](<span class="hljs-keyword">auto</span> a, <span class="hljs-keyword">auto</span> b)  <span class="hljs-comment">// &#x5B9A;&#x4E49;&#x4E00;&#x4E2A;lambda&#xFF0C;&#x7528;&#x6765;&#x6BD4;&#x8F83;&#x5927;&#x5C0F;</span>
{   
    <span class="hljs-keyword">return</span> a &gt; b;                <span class="hljs-comment">// &#x5B9A;&#x4E49;&#x5927;&#x4E8E;&#x5173;&#x7CFB;</span>
};  

<span class="hljs-built_in">set</span>&lt;<span class="hljs-keyword">int</span>, <span class="hljs-keyword">decltype</span>(comp)&gt; gs(comp)  <span class="hljs-comment">// &#x4F7F;&#x7528;decltype&#x5F97;&#x5230;lambda&#x7684;&#x7C7B;&#x578B;</span>

<span class="hljs-built_in">std</span>::copy(begin(s), end(s),          <span class="hljs-comment">// &#x62F7;&#x8D1D;&#x7B97;&#x6CD5;&#xFF0C;&#x62F7;&#x8D1D;&#x6570;&#x636E;</span>
          inserter(gs, gs.end()));  <span class="hljs-comment">// &#x4F7F;&#x7528;&#x63D2;&#x5165;&#x8FED;&#x4EE3;&#x5668;</span>

<span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span>&amp; x : gs) {                <span class="hljs-comment">// &#x8303;&#x56F4;&#x5FAA;&#x73AF;&#x8F93;&#x51FA;&#x5143;&#x7D20;</span>
    <span class="hljs-built_in">cout</span> &lt;&lt; x &lt;&lt; <span class="hljs-string">&quot;,&quot;</span>;                <span class="hljs-comment">// &#x4ECE;&#x5927;&#x5230;&#x5C0F;&#x6392;&#x5E8F;&#xFF0C;9,7,3</span>
}
</code></pre>
<h3 id="19---&#x4F7F;&#x7528;&#x65E0;&#x5E8F;&#x5BB9;&#x5668;&#x63D2;&#x5165;&#x81EA;&#x5B9A;&#x4E49;&#x5BF9;&#x8C61;&#x8981;&#x600E;&#x4E48;&#x505A;&#xFF1F;">19 - &#x4F7F;&#x7528;&#x65E0;&#x5E8F;&#x5BB9;&#x5668;&#x63D2;&#x5165;&#x81EA;&#x5B9A;&#x4E49;&#x5BF9;&#x8C61;&#x8981;&#x600E;&#x4E48;&#x505A;&#xFF1F;</h3>
<p>&#x65E0;&#x5E8F;&#x5BB9;&#x5668;&#x4E5F;&#x6709;&#x56DB;&#x79CD;&#xFF0C;&#x540D;&#x5B57;&#x91CC;&#x4E5F;&#x6709; set &#x548C; map&#xFF0C;&#x53EA;&#x662F;&#x52A0;&#x4E0A;&#x4E86; unordered&#xFF08;&#x65E0;&#x5E8F;&#xFF09;&#x524D;&#x7F00;&#xFF0C;&#x5206;&#x522B;&#x662F;unordered_set/unordered_multiset&#x3001;unordered_map/unordered_multimap&#x3002;</p>
<p>&#x65E0;&#x5E8F;&#x5BB9;&#x5668;&#x867D;&#x7136;&#x4E0D;&#x8981;&#x6C42;&#x987A;&#x5E8F;&#xFF0C;&#x4F46;&#x662F;&#x5BF9; key &#x7684;&#x8981;&#x6C42;&#x53CD;&#x800C;&#x6BD4;&#x6709;&#x5E8F;&#x5BB9;&#x5668;&#x66F4;&#x201C;&#x82DB;&#x523B;&#x201D;&#x4E00;&#x4E9B;&#xFF0C;&#x4F8B;&#x5982;unordered_map &#x7684;&#x58F0;&#x660E;&#xFF1A;</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">template</span>&lt;
    <span class="hljs-keyword">class</span> Key,                          <span class="hljs-comment">// &#x7B2C;&#x4E00;&#x4E2A;&#x6A21;&#x677F;&#x53C2;&#x6570;&#x662F;key&#x7C7B;&#x578B;</span>
    <span class="hljs-keyword">class</span> T,                            <span class="hljs-comment">// &#x7B2C;&#x4E8C;&#x4E2A;&#x6A21;&#x677F;&#x53C2;&#x6570;&#x662F;&#x5143;&#x7D20;&#x7C7B;&#x578B;</span>
    <span class="hljs-keyword">class</span> Hash = <span class="hljs-built_in">std</span>::hash&lt;Key&gt;,        <span class="hljs-comment">// &#x8BA1;&#x7B97;&#x6563;&#x5217;&#x503C;&#x7684;&#x51FD;&#x6570;&#x5BF9;&#x8C61;</span>
    <span class="hljs-keyword">class</span> KeyEqual = <span class="hljs-built_in">std</span>::equal_to&lt;Key&gt; <span class="hljs-comment">// &#x76F8;&#x7B49;&#x6BD4;&#x8F83;&#x51FD;&#x6570;</span>
&gt; <span class="hljs-keyword">class</span> <span class="hljs-built_in">unordered_map</span>;
</code></pre>
<p><strong>&#x5B83;&#x8981;&#x6C42; key &#x5177;&#x5907;&#x4E24;&#x4E2A;&#x6761;&#x4EF6;&#xFF0C;&#x4E00;&#x662F;&#x53EF;&#x4EE5;&#x8BA1;&#x7B97; hash &#x503C;&#xFF0C;&#x4E8C;&#x662F;&#x80FD;&#x591F;&#x6267;&#x884C;&#x76F8;&#x7B49;&#x6BD4;&#x8F83;&#x64CD;&#x4F5C;&#x3002;</strong></p>
<p>&#x7B2C;&#x4E00;&#x4E2A;&#x662F;&#x56E0;&#x4E3A;&#x6563;&#x5217;&#x8868;&#x7684;&#x8981;&#x6C42;&#xFF0C;&#x53EA;&#x6709;&#x8BA1;&#x7B97; hash &#x503C;&#x624D;&#x80FD;&#x653E;&#x5165;&#x6563;&#x5217;&#x8868;&#xFF0C;&#x7B2C;&#x4E8C;&#x4E2A;&#x5219;&#x662F;&#x56E0;&#x4E3A; hash &#x503C;&#x53EF;&#x80FD;&#x4F1A;&#x51B2;&#x7A81;&#xFF0C;&#x6240;&#x4EE5;&#x5F53; hash &#x503C;&#x76F8;&#x540C;&#x65F6;&#xFF0C;&#x5C31;&#x8981;&#x6BD4;&#x8F83;&#x771F;&#x6B63;&#x7684; key &#x503C;&#x3002;</p>
<p><strong>&#x4E0E;&#x6709;&#x5E8F;&#x5BB9;&#x5668;&#x4E00;&#x6837;&#xFF0C;&#x8981;&#x628A;&#x81EA;&#x5B9A;&#x4E49;&#x7C7B;&#x578B;&#x4F5C;&#x4E3A; key &#x653E;&#x5165;&#x65E0;&#x5E8F;&#x5BB9;&#x5668;&#xFF0C;&#x5FC5;&#x987B;&#x8981;&#x5B9E;&#x73B0;&#x8FD9;&#x4E24;&#x4E2A;&#x51FD;&#x6570;&#xFF1A;</strong></p>
<ul>
<li><strong>&#x201C;==&#x201D;&#x51FD;&#x6570; &#xFF1A;</strong>&#x53EF;&#x4EE5;&#x7528;&#x4E0E;&#x201C;&lt;&#x201D;&#x51FD;&#x6570;&#x7C7B;&#x4F3C;&#x7684;&#x65B9;&#x5F0F;&#xFF0C;&#x901A;&#x8FC7;&#x91CD;&#x8F7D;&#x64CD;&#x4F5C;&#x7B26;&#x6765;&#x5B9E;&#x73B0;</li>
</ul>
<pre><code class="lang-cpp"><span class="hljs-keyword">bool</span> <span class="hljs-keyword">operator</span>==(<span class="hljs-keyword">const</span> Point&amp; a, <span class="hljs-keyword">const</span> Point&amp; b)
{
    <span class="hljs-keyword">return</span> a.x == b.x;              <span class="hljs-comment">// &#x81EA;&#x5B9A;&#x4E49;&#x76F8;&#x7B49;&#x6BD4;&#x8F83;&#x8FD0;&#x7B97;</span>
}
</code></pre>
<ul>
<li><strong>&#x6563;&#x5217;&#x51FD;&#x6570;&#xFF1A;</strong>&#x53EF;&#x4EE5;&#x7528;&#x51FD;&#x6570;&#x5BF9;&#x8C61;&#x6216;&#x8005; lambda &#x8868;&#x8FBE;&#x5F0F;&#x5B9E;&#x73B0;&#xFF0C;&#x5185;&#x90E8;&#x6700;&#x597D;&#x8C03;&#x7528;&#x6807;&#x51C6;&#x7684; std::hash &#x51FD;&#x6570;&#x5BF9;&#x8C61;&#xFF0C;&#x800C;&#x4E0D;&#x8981;&#x81EA;&#x5DF1;&#x76F4;&#x63A5;&#x8BA1;&#x7B97;&#xFF0C;&#x5426;&#x5219;&#x5F88;&#x5BB9;&#x6613;&#x9020;&#x6210; hash &#x51B2;&#x7A81;&#xFF1A;</li>
</ul>
<pre><code class="lang-cpp"><span class="hljs-keyword">auto</span> hasher = [](<span class="hljs-keyword">const</span> <span class="hljs-keyword">auto</span>&amp; p)    <span class="hljs-comment">// &#x5B9A;&#x4E49;&#x4E00;&#x4E2A;lambda&#x8868;&#x8FBE;&#x5F0F;</span>
{
    <span class="hljs-keyword">return</span> <span class="hljs-built_in">std</span>::hash&lt;<span class="hljs-keyword">int</span>&gt;()(p.x);  <span class="hljs-comment">// &#x8C03;&#x7528;&#x6807;&#x51C6;hash&#x51FD;&#x6570;&#x5BF9;&#x8C61;&#x8BA1;&#x7B97;</span>
};
</code></pre>
<p>&#x6709;&#x4E86;&#x76F8;&#x7B49;&#x51FD;&#x6570;&#x548C;&#x6563;&#x5217;&#x51FD;&#x6570;&#xFF0C;&#x81EA;&#x5B9A;&#x4E49;&#x7C7B;&#x578B;&#x4E5F;&#x5C31;&#x53EF;&#x4EE5;&#x653E;&#x8FDB;&#x65E0;&#x5E8F;&#x5BB9;&#x5668;&#x4E86;&#xFF1A;</p>
<pre><code class="lang-cpp"><span class="hljs-built_in">unordered_set</span>&lt;Point, <span class="hljs-keyword">decltype</span>(hasher)&gt; s(<span class="hljs-number">10</span>, hasher);

s.emplace(<span class="hljs-number">7</span>);
s.emplace(<span class="hljs-number">3</span>);
</code></pre>
<h3 id="20---&#x5BB9;&#x5668;&#x5185;&#x5220;&#x9664;&#x4E00;&#x4E2A;&#x5143;&#x7D20;">20 - &#x5BB9;&#x5668;&#x5185;&#x5220;&#x9664;&#x4E00;&#x4E2A;&#x5143;&#x7D20;</h3>
<ul>
<li><strong>&#x5BF9;&#x4E8E;&#x987A;&#x5E8F;&#x5BB9;&#x5668;<code>vector</code>,<code>deque</code>&#x6765;&#x8BF4;</strong>&#xFF0C;&#x4F7F;&#x7528;<code>erase(itertor)</code>&#x540E;&#xFF0C;&#x540E;&#x8FB9;&#x7684;&#x6BCF;&#x4E2A;&#x5143;&#x7D20;&#x7684;&#x8FED;&#x4EE3;&#x5668;&#x90FD;&#x4F1A;&#x5931;&#x6548;&#xFF08;<code>list</code>&#x9664;&#x5916;&#xFF09;&#xFF0C;&#x4F46;&#x662F;&#x540E;&#x8FB9;&#x6BCF;&#x4E2A;&#x5143;&#x7D20;&#x90FD;&#x4F1A;&#x5F80;&#x524D;&#x79FB;&#x52A8;&#x4E00;&#x4E2A;&#x4F4D;&#x7F6E;&#xFF0C;<code>erase</code> &#x4F1A;&#x8FD4;&#x56DE;&#x4E0B;&#x4E00;&#x4E2A;&#x6709;&#x6548;&#x7684;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x89C1;&#x5982;&#x4E0B;&#x4EE3;&#x7801;&#xFF0C;&#x8FD4;&#x56DE;&#x7684;&#x662F;&#x5220;&#x9664;&#x7684;&#x540E;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x7684;&#x8FED;&#x4EE3;&#x5668;</li>
</ul>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span>
</span>{
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; v{<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>};
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> it = v.begin(); it != v.end(); ++it)
        <span class="hljs-built_in">cout</span> &lt;&lt; *it &lt;&lt; <span class="hljs-string">&quot; &quot;</span>;
    <span class="hljs-keyword">auto</span> it = v.begin() + <span class="hljs-number">1</span>;
    <span class="hljs-keyword">auto</span> res = v.erase(it); 
    <span class="hljs-built_in">cout</span> &lt;&lt; <span class="hljs-built_in">endl</span> &lt;&lt; *res &lt;&lt; <span class="hljs-built_in">endl</span>;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}
</code></pre>
<p>&#x8F93;&#x51FA;&#xFF1A;</p>
<pre><code>1 2 3
3
</code></pre><ul>
<li><p><strong>&#x5BF9;&#x4E8E;&#x5173;&#x8054;&#x5BB9;&#x5668;<code>map</code> ,<code>set</code> &#x6765;&#x8BF4;</strong>&#xFF0C;&#x4F7F;&#x7528;&#x4E86;<code>erase(iterator)</code>&#x540E;&#xFF0C;&#x5F53;&#x524D;&#x5143;&#x7D20;&#x7684;&#x8FED;&#x4EE3;&#x5668;&#x5931;&#x6548;&#xFF0C;&#x4F46;&#x662F;&#x5176;&#x7ED3;&#x6784;&#x662F;&#x7EA2;&#x9ED1;&#x6811;&#xFF0C;&#x5220;&#x9664;&#x5F53;&#x524D;&#x5143;&#x7D20;&#x4E0D;&#x4F1A;&#x5F71;&#x54CD;&#x5230;&#x4E0B;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x7684;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x8FD4;&#x56DE;&#x503C;&#x662F;<code>void</code>&#xFF0C;&#x6240;&#x4EE5;&#x8981;&#x91C7;&#x7528;<code>erase(it++)</code>&#x7684;&#x65B9;&#x5F0F;&#x5220;&#x9664;&#x8FED;&#x4EE3;&#x5668;&#xFF1B;&#x8FD9;&#x6837;<code>it</code>&#x5C31;&#x8BB0;&#x5F55;&#x4E86;&#x4E0B;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x7684;&#x8FED;&#x4EE3;&#x5668;</p>
</li>
<li><p><strong>&#x5BF9;&#x4E8E;list&#x6765;&#x8BF4;</strong>&#xFF0C;&#x5B83;&#x4F7F;&#x7528;&#x4E86;&#x4E0D;&#x8FDE;&#x7EED;&#x5206;&#x914D;&#x7684;&#x5185;&#x5B58;&#xFF0C;&#x5E76;&#x4E14;&#x5B83;&#x7684;<code>erase</code>&#x65B9;&#x6CD5;&#x4E5F;&#x4F1A;&#x8FD4;&#x56DE;&#x4E0B;&#x4E00;&#x4E2A;&#x6709;&#x6548;&#x7684;iterator&#xFF0C;&#x4E0B;&#x8FF0;&#x4E24;&#x79CD;&#x5199;&#x6CD5;&#x5747;&#x53EF;</p>
</li>
</ul>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span>
</span>{
    <span class="hljs-built_in">list</span>&lt;<span class="hljs-keyword">int</span>&gt; lst{<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>, <span class="hljs-number">4</span>, <span class="hljs-number">5</span>};
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> it = lst.begin(); it != lst.end(); ++it)
        <span class="hljs-built_in">cout</span> &lt;&lt; *it &lt;&lt; <span class="hljs-string">&quot; &quot;</span>;
    <span class="hljs-keyword">auto</span> res1 = lst.erase(lst.begin());  <span class="hljs-comment">// &#x5199;&#x6CD5;&#x4E00;</span>
    <span class="hljs-built_in">cout</span> &lt;&lt; <span class="hljs-built_in">endl</span>
         &lt;&lt; *res1 &lt;&lt; <span class="hljs-built_in">endl</span>;

    <span class="hljs-keyword">auto</span> res2 = lst.begin();
    lst.erase(res2++);                   <span class="hljs-comment">// &#x5199;&#x6CD5;&#x4E8C;</span>
    <span class="hljs-built_in">cout</span> &lt;&lt; *res2 &lt;&lt; <span class="hljs-built_in">endl</span>;    
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> it = lst.begin(); it != lst.end(); ++it)
        <span class="hljs-built_in">cout</span> &lt;&lt; *it &lt;&lt; <span class="hljs-string">&quot; &quot;</span>;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}
</code></pre>
<p>&#x8F93;&#x51FA;&#xFF1A;</p>
<pre><code>1 2 3 4 5 
2
3
3 4 5
</code></pre><h3 id="21---&#x8FED;&#x4EE3;&#x5668;--it-&#x4E0E;-it">21 - &#x8FED;&#x4EE3;&#x5668; ++ it &#x4E0E; it++</h3>
<ul>
<li>&#x524D;&#x7F6E;&#xFF08;++ it&#xFF09;&#x8FD4;&#x56DE;&#x4E00;&#x4E2A;&#x5F15;&#x7528;&#xFF0C;&#x540E;&#x7F6E;&#xFF08; it ++&#xFF09;&#x8FD4;&#x56DE;&#x4E00;&#x4E2A;&#x5BF9;&#x8C61;</li>
<li>&#x524D;&#x7F6E;&#xFF08;++ it&#xFF09;&#x4E0D;&#x4F1A;&#x4EA7;&#x751F;&#x4E34;&#x65F6;&#x53D8;&#x91CF;&#xFF0C;&#x540E;&#x7F6E;&#xFF08; it ++&#xFF09;&#x5FC5;&#x987B;&#x4EA7;&#x751F;&#x4E34;&#x65F6;&#x5BF9;&#x8C61;&#xFF0C;&#x4E34;&#x65F6;&#x5BF9;&#x8C61;&#x4F1A;&#x5BFC;&#x81F4;&#x6548;&#x7387;&#x964D;&#x4F4E;</li>
</ul>
<pre><code class="lang-cpp"><span class="hljs-comment">// &#x524D;&#x7F00;&#x5F62;&#x5F0F;&#xFF1A;</span>
<span class="hljs-keyword">int</span>&amp; <span class="hljs-keyword">int</span>::<span class="hljs-keyword">operator</span>++() <span class="hljs-comment">//&#x8FD9;&#x91CC;&#x8FD4;&#x56DE;&#x7684;&#x662F;&#x4E00;&#x4E2A;&#x5F15;&#x7528;&#x5F62;&#x5F0F;&#xFF0C;&#x5C31;&#x662F;&#x8BF4;&#x51FD;&#x6570;&#x8FD4;&#x56DE;&#x503C;&#x4E5F;&#x53EF;&#x4EE5;&#x4F5C;&#x4E3A;&#x4E00;&#x4E2A;&#x5DE6;&#x503C;&#x4F7F;&#x7528;</span>
{<span class="hljs-comment">//&#x51FD;&#x6570;&#x672C;&#x8EAB;&#x65E0;&#x53C2;&#xFF0C;&#x610F;&#x5473;&#x7740;&#x662F;&#x5728;&#x81EA;&#x8EAB;&#x7A7A;&#x95F4;&#x5185;&#x589E;&#x52A0;1&#x7684;</span>
  *<span class="hljs-keyword">this</span> += <span class="hljs-number">1</span>;  <span class="hljs-comment">// &#x589E;&#x52A0;</span>
  <span class="hljs-keyword">return</span> *<span class="hljs-keyword">this</span>;  <span class="hljs-comment">// &#x53D6;&#x56DE;&#x503C;</span>
}

<span class="hljs-comment">//&#x540E;&#x7F00;&#x5F62;&#x5F0F;:&#x51FD;&#x6570;&#x8FD4;&#x56DE;&#x503C;&#x662F;&#x4E00;&#x4E2A;&#x975E;&#x5DE6;&#x503C;&#x578B;&#x7684;&#xFF0C;&#x4E0E;&#x524D;&#x7F00;&#x5F62;&#x5F0F;&#x7684;&#x5DEE;&#x522B;&#x6240;&#x5728;&#x3002;</span>
<span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> <span class="hljs-keyword">int</span>::<span class="hljs-keyword">operator</span>++(<span class="hljs-keyword">int</span>)  <span class="hljs-comment">//&#x51FD;&#x6570;&#x5E26;&#x53C2;&#xFF0C;&#x8BF4;&#x660E;&#x6709;&#x53E6;&#x5916;&#x7684;&#x7A7A;&#x95F4;&#x5F00;&#x8F9F;</span>
{
  <span class="hljs-keyword">int</span> oldValue = *<span class="hljs-keyword">this</span>;  <span class="hljs-comment">// &#x53D6;&#x56DE;&#x503C;</span>
  ++ (*<span class="hljs-keyword">this</span>);  <span class="hljs-comment">// &#x589E;&#x52A0;</span>
  <span class="hljs-keyword">return</span> oldValue;  <span class="hljs-comment">// &#x8FD4;&#x56DE;&#x88AB;&#x53D6;&#x56DE;&#x7684;&#x503C;</span>
}
</code></pre>
<h3 id="22---&#x6307;&#x9488;&#x548C;&#x8FED;&#x4EE3;&#x5668;">22 - &#x6307;&#x9488;&#x548C;&#x8FED;&#x4EE3;&#x5668;</h3>
<h4 id="&#x8FED;&#x4EE3;&#x5668;&#xFF1A;">&#x8FED;&#x4EE3;&#x5668;&#xFF1A;</h4>
<ul>
<li>Iterator&#xFF08;&#x8FED;&#x4EE3;&#x5668;&#xFF09;&#x662F;&#x4E00;&#x79CD;&#x62BD;&#x8C61;&#x7684;&#x8BBE;&#x8BA1;&#x7406;&#x5FF5;&#xFF0C;&#x901A;&#x8FC7;&#x8FED;&#x4EE3;&#x5668;&#x53EF;&#x4EE5;&#x5728;&#x4E0D;&#x4E86;&#x89E3;&#x5BB9;&#x5668;&#x5185;&#x90E8;&#x539F;&#x7406;&#x7684;&#x60C5;&#x51B5;&#x4E0B;&#x904D;&#x5386;&#x5BB9;&#x5668;&#x3002;</li>
</ul>
<h4 id="&#x8FED;&#x4EE3;&#x5668;&#x4E0E;&#x6307;&#x9488;&#x7684;&#x533A;&#x522B;&#xFF1A;">&#x8FED;&#x4EE3;&#x5668;&#x4E0E;&#x6307;&#x9488;&#x7684;&#x533A;&#x522B;&#xFF1A;</h4>
<ul>
<li><strong>&#x8FED;&#x4EE3;&#x5668;&#x4E0D;&#x662F;&#x6307;&#x9488;&#xFF0C;&#x662F;&#x7C7B;&#x6A21;&#x677F;</strong>&#xFF0C;&#x8868;&#x73B0;&#x7684;&#x50CF;&#x6307;&#x9488;&#x3002;&#x5B83;&#x53EA;&#x662F;&#x6A21;&#x62DF;&#x4E86;&#x6307;&#x9488;&#x7684;&#x4E00;&#x4E9B;&#x529F;&#x80FD;&#xFF0C;&#x901A;&#x8FC7;&#x91CD;&#x8F7D;&#x4E86;&#x6307;&#x9488;&#x7684;&#x4E00;&#x4E9B;&#x64CD;&#x4F5C;&#x7B26;&#xFF0C;<code>-&gt;</code>&#x3001;<code>*</code>&#x3001;<code>++</code>&#x3001;<code>--</code>&#x7B49;&#x3002;&#x8FED;&#x4EE3;&#x5668;&#x5C01;&#x88C5;&#x4E86;&#x6307;&#x9488;&#xFF0C;&#x662F;&#x4E00;&#x4E2A;<strong>&#x53EF;&#x904D;&#x5386;STL&#xFF08; Standard TemplateLibrary&#xFF09;&#x5BB9;&#x5668;&#x5185;&#x5168;&#x90E8;&#x6216;&#x90E8;&#x5206;&#x5143;&#x7D20;</strong>&#x7684;&#x5BF9;&#x8C61;&#xFF0C; &#x672C;&#x8D28;&#x662F;&#x5C01;&#x88C5;&#x4E86;&#x539F;&#x751F;&#x6307;&#x9488;&#xFF0C;&#x662F;&#x6307;&#x9488;&#x6982;&#x5FF5;&#x7684;&#x4E00;&#x79CD;&#x63D0;&#x5347;&#xFF08;lift&#xFF09;&#xFF0C;&#x63D0;&#x4F9B;&#x4E86;&#x6BD4;&#x6307;&#x9488;&#x66F4;&#x9AD8;&#x7EA7;&#x7684;&#x884C;&#x4E3A;&#xFF0C;&#x76F8;&#x5F53;&#x4E8E;&#x4E00;&#x79CD;&#x667A;&#x80FD;&#x6307;&#x9488;&#xFF0C;&#x5B83;&#x53EF;&#x4EE5;&#x6839;&#x636E;&#x4E0D;&#x540C;&#x7C7B;&#x578B;&#x7684;&#x6570;&#x636E;&#x7ED3;&#x6784;&#x6765;&#x5B9E;&#x73B0;&#x4E0D;&#x540C;&#x7684;<code>++</code>&#xFF0C;<code>--</code>&#x7B49;&#x64CD;&#x4F5C;&#x3002;</li>
<li>&#x8FED;&#x4EE3;&#x5668;&#x8FD4;&#x56DE;&#x7684;&#x662F;&#x5BF9;&#x8C61;&#x5F15;&#x7528;&#x800C;&#x4E0D;&#x662F;&#x5BF9;&#x8C61;&#x7684;&#x503C;&#xFF0C;&#x6240;&#x4EE5;cout &#x53EA;&#x80FD;&#x8F93;&#x51FA;&#x8FED;&#x4EE3;&#x5668;&#x4F7F;&#x7528;<code>*</code>&#x53D6;&#x503C;&#x540E;&#x7684;&#x503C;&#x800C;&#x4E0D;&#x80FD;&#x76F4;&#x63A5;&#x8F93;&#x51FA;&#x5176;&#x81EA;&#x8EAB;&#x3002;</li>
</ul>
<h4 id="&#x8FED;&#x4EE3;&#x5668;&#x4EA7;&#x751F;&#x7684;&#x539F;&#x56E0;">&#x8FED;&#x4EE3;&#x5668;&#x4EA7;&#x751F;&#x7684;&#x539F;&#x56E0;</h4>
<ul>
<li>Iterator &#x7C7B;&#x7684;&#x8BBF;&#x95EE;&#x65B9;&#x5F0F;&#x5C31;&#x662F;&#x628A;&#x4E0D;&#x540C;&#x96C6;&#x5408;&#x7C7B;&#x7684;&#x8BBF;&#x95EE;&#x903B;&#x8F91;&#x62BD;&#x8C61;&#x51FA;&#x6765;&#xFF0C;&#x4F7F;&#x5F97;&#x4E0D;&#x7528;&#x66B4;&#x9732;&#x96C6;&#x5408;&#x5185;&#x90E8;&#x7684;&#x7ED3;&#x6784;&#x800C;&#x8FBE;&#x5230;&#x5FAA;&#x73AF;&#x904D;&#x5386;&#x96C6;&#x5408;&#x7684;&#x6548;&#x679C;&#x3002;</li>
</ul>
<h3 id="23---&#x5982;&#x679C;&#x5728;&#x5171;&#x4EAB;&#x5185;&#x5B58;&#x4E0A;&#x4F7F;&#x7528;stl&#x6807;&#x51C6;&#x5E93;&#xFF1F;">23 - &#x5982;&#x679C;&#x5728;&#x5171;&#x4EAB;&#x5185;&#x5B58;&#x4E0A;&#x4F7F;&#x7528;STL&#x6807;&#x51C6;&#x5E93;&#xFF1F;</h3>
<p>&#x5047;&#x8BBE;&#x8FDB;&#x7A0B;A&#x5728;&#x5171;&#x4EAB;&#x5185;&#x5B58;&#x4E2D;&#x653E;&#x5165;&#x4E86;&#x6570;&#x4E2A;&#x5BB9;&#x5668;&#xFF0C;&#x8FDB;&#x7A0B;B&#x5982;&#x4F55;&#x627E;&#x5230;&#x8FD9;&#x4E9B;&#x5BB9;&#x5668;&#x5462;&#xFF1F;</p>
<p>&#x4E00;&#x4E2A;&#x65B9;&#x6CD5;&#x662F;&#x8FDB;&#x7A0B;A&#x628A;&#x5BB9;&#x5668;&#x653E;&#x5728;&#x5171;&#x4EAB;&#x5185;&#x5B58;&#x7684;&#x786E;&#x5B9A;&#x5730;&#x5740;&#x4E0A;&#xFF08;fixed offsets&#xFF09;&#xFF0C;&#x5219;&#x8FDB;&#x7A0B;&#x53EF;&#x4EE5;&#x4ECE;&#x8BE5;&#x5DF2;&#x77E5;&#x5730;&#x5740;&#x4E0A;&#x83B7;&#x53D6;&#x5BB9;&#x5668;&#x3002;</p>
<p>&#x53E6;&#x4E00;&#x4E2A;&#x6539;&#x8FDB;&#x7684;&#x529E;&#x6CD5;&#x662F;&#xFF0C;&#x8FDB;&#x7A0B;A&#x73B0;&#x5728;&#x5171;&#x4EAB;&#x5185;&#x6DA6;&#x67D0;&#x5FEB;&#x786E;&#x5B9A;&#x5730;&#x5740;&#x4E0A;&#x653E;&#x4E00;&#x4E2A;map&#x5BB9;&#x5668;&#xFF0C;&#x7136;&#x540E;&#x8FDB;&#x7A0B;A&#x518D;&#x521B;&#x5EFA;&#x5176;&#x4ED6;&#x5BB9;&#x5668;&#xFF0C;&#x7136;&#x540E;&#x7ED9;&#x5B83;&#x53D6;&#x4E2A;&#x540D;&#x5B57;&#xFF0C;&#x548C;&#x5730;&#x5740;&#x4E00;&#x5E76;&#x4FDD;&#x5B58;&#x5230;&#x8FD9;&#x4E2A;map&#x5BB9;&#x5668;&#x91CC;&#x3002;</p>
<p>&#x8FDB;&#x7A0B;B&#x77E5;&#x9053;&#x5982;&#x4F55;&#x83B7;&#x53D6;&#x8BE5;&#x4FDD;&#x5B58;&#x4E86;&#x5730;&#x5740;&#x6620;&#x5C04;&#x7684;map&#x5BB9;&#x5668;&#xFF0C;&#x7136;&#x540E;&#x7EDF;&#x4E00;&#x518D;&#x6839;&#x636E;&#x540D;&#x5B57;&#x53D6;&#x5F97;&#x5176;&#x4ED6;&#x5BB9;&#x5668;&#x7684;&#x5730;&#x5740;&#x3002;</p>
<h3 id="24---&#x5E38;&#x7528;&#x7B97;&#x6CD5;">24 - &#x5E38;&#x7528;&#x7B97;&#x6CD5;</h3>
<h4 id="241-&#x51FD;&#x6570;&#x5F0F;&#x7F16;&#x7A0B;">24.1 &#x51FD;&#x6570;&#x5F0F;&#x7F16;&#x7A0B;</h4>
<p>&#x7EDF;&#x8BA1;&#x67D0;&#x4E2A;&#x5143;&#x7D20;&#x7684;&#x51FA;&#x73B0;&#x6B21;&#x6570;&#xFF1A;</p>
<pre><code class="lang-cpp"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; v = {<span class="hljs-number">1</span>,<span class="hljs-number">3</span>,<span class="hljs-number">1</span>,<span class="hljs-number">7</span>,<span class="hljs-number">5</span>};    <span class="hljs-comment">// vector&#x5BB9;&#x5668;</span>

<span class="hljs-keyword">auto</span> n1 = <span class="hljs-built_in">std</span>::count(          <span class="hljs-comment">// count&#x7B97;&#x6CD5;&#x8BA1;&#x7B97;&#x5143;&#x7D20;&#x7684;&#x6570;&#x91CF; </span>
    begin(v), end(v), <span class="hljs-number">1</span>        <span class="hljs-comment">// begin()&#x3001;end()&#x83B7;&#x53D6;&#x5BB9;&#x5668;&#x7684;&#x8303;&#x56F4;</span>
);
</code></pre>
<p>&#x4F7F;&#x7528;&#x5C31;&#x5730;&#x5B9A;&#x4E49;&#x51FD;&#x6570;&#x7684;lambda&#x8868;&#x8FBE;&#x5F0F;&#xFF0C;&#x51FD;&#x6570;&#x5F0F;&#x7F16;&#x7A0B;&#xFF0C;&#x7EDF;&#x8BA1;&#x5927;&#x4E8E;2&#x7684;&#x5143;&#x7D20;&#x4E2A;&#x6570;</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">auto</span> n = <span class="hljs-built_in">std</span>::count_if(      <span class="hljs-comment">// count_if&#x7B97;&#x6CD5;&#x8BA1;&#x7B97;&#x5143;&#x7D20;&#x7684;&#x6570;&#x91CF;</span>
    begin(v), end(v),       <span class="hljs-comment">// begin()&#x3001;end()&#x83B7;&#x53D6;&#x5BB9;&#x5668;&#x7684;&#x8303;&#x56F4;</span>
    [](<span class="hljs-keyword">auto</span> x) {            <span class="hljs-comment">// &#x5B9A;&#x4E49;&#x4E00;&#x4E2A;lambda&#x8868;&#x8FBE;&#x5F0F;</span>
        <span class="hljs-keyword">return</span> x &gt; <span class="hljs-number">2</span>;       <span class="hljs-comment">// &#x5224;&#x65AD;&#x6761;&#x4EF6;</span>
    }
);                          <span class="hljs-comment">// &#x5927;&#x51FD;&#x6570;&#x91CC;&#x9762;&#x5957;&#x4E86;&#x4E09;&#x4E2A;&#x5C0F;&#x51FD;&#x6570;</span>
</code></pre>
<h4 id="242-&#x8FED;&#x4EE3;&#x5668;&#x4F7F;&#x7528;">24.2 &#x8FED;&#x4EE3;&#x5668;&#x4F7F;&#x7528;</h4>
<p>&#x5BB9;&#x5668;&#x4E00;&#x822C;&#x4F1A;&#x63D0;&#x4F9B;begin()&#xFF0C;end()&#x51FD;&#x6570;&#xFF0C;&#x4F46;&#x66F4;&#x5EFA;&#x8BAE;&#x4F7F;&#x7528;&#x66F4;&#x52A0;&#x901A;&#x7528;&#x7684;&#x5168;&#x5C40;&#x51FD;&#x6570;begin()&#xFF0C;end()&#xFF0C;&#x53E6;&#x5916;&#x8FD8;&#x6709;cbegin(), rbegin()</p>
<pre><code class="lang-cpp"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; v = {<span class="hljs-number">1</span>,<span class="hljs-number">2</span>,<span class="hljs-number">3</span>,<span class="hljs-number">4</span>,<span class="hljs-number">5</span>};    <span class="hljs-comment">// vector&#x5BB9;&#x5668;</span>

<span class="hljs-keyword">auto</span> iter1 = v.begin();        <span class="hljs-comment">// &#x6210;&#x5458;&#x51FD;&#x6570;&#x83B7;&#x53D6;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x81EA;&#x52A8;&#x7C7B;&#x578B;&#x63A8;&#x5BFC;</span>
<span class="hljs-keyword">auto</span> iter2 = v.end();

<span class="hljs-keyword">auto</span> iter3 = <span class="hljs-built_in">std</span>::begin(v);   <span class="hljs-comment">// &#x5168;&#x5C40;&#x51FD;&#x6570;&#x83B7;&#x53D6;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x81EA;&#x52A8;&#x7C7B;&#x578B;&#x63A8;&#x5BFC;</span>
<span class="hljs-keyword">auto</span> iter4 = <span class="hljs-built_in">std</span>::end(v);

<span class="hljs-keyword">auto</span> iter5 = v.rbegin();     <span class="hljs-comment">// &#x53CD;&#x5411;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x524D;&#x5F00;&#x540E;&#x95ED;&#x533A;&#x95F4;</span>
<span class="hljs-keyword">auto</span> iter6 = v.rend();         <span class="hljs-comment">//</span>

<span class="hljs-keyword">auto</span> iter7 = v.cbegin();     <span class="hljs-comment">// &#x5E38;&#x91CF;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x53EA;&#x8BFB;</span>
</code></pre>
<p>&#x8FED;&#x4EE3;&#x5668;&#x548C;&#x6307;&#x9488;&#x7C7B;&#x4F3C;&#xFF0C;&#x4E5F;&#x53EF;&#x4EE5;&#x524D;&#x8FDB;&#x548C;&#x540E;&#x9000;&#xFF0C;&#x4F46;&#x4E0D;&#x80FD;&#x5047;&#x8BBE;&#x5B83;&#x4E00;&#x5B9A;&#x652F;&#x6301;&#x201C;++&#x201D;&#x201C;--&#x201D;&#x64CD;&#x4F5C;&#x7B26;&#xFF0C;&#x6700;&#x597D;&#x4E5F;&#x8981;&#x7528;&#x51FD;&#x6570;&#x6765;&#x64CD;&#x4F5C;&#xFF0C;&#x5E38;&#x7528;&#x7684;&#x6709;&#x8FD9;&#x4E48;&#x51E0;&#x4E2A;&#xFF1A;</p>
<ul>
<li>distance()&#xFF0C;&#x8BA1;&#x7B97;&#x4E24;&#x4E2A;&#x8FED;&#x4EE3;&#x5668;&#x4E4B;&#x95F4;&#x7684;&#x8DDD;&#x79BB;&#xFF1B;</li>
<li>advance()&#xFF0C;&#x524D;&#x8FDB;&#x6216;&#x8005;&#x540E;&#x9000; N &#x6B65;&#xFF1B;</li>
<li>next()/prev()&#xFF0C;&#x8BA1;&#x7B97;&#x8FED;&#x4EE3;&#x5668;&#x524D;&#x540E;&#x7684;&#x67D0;&#x4E2A;&#x4F4D;&#x7F6E;&#x3002;</li>
</ul>
<pre><code class="lang-cpp"><span class="hljs-built_in">array</span>&lt;<span class="hljs-keyword">int</span>, 5&gt; arr = {<span class="hljs-number">0</span>,<span class="hljs-number">1</span>,<span class="hljs-number">2</span>,<span class="hljs-number">3</span>,<span class="hljs-number">4</span>};  <span class="hljs-comment">// array&#x9759;&#x6001;&#x6570;&#x7EC4;&#x5BB9;&#x5668;</span>

<span class="hljs-keyword">auto</span> b = begin(arr);          <span class="hljs-comment">// &#x5168;&#x5C40;&#x51FD;&#x6570;&#x83B7;&#x53D6;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x9996;&#x7AEF;</span>
<span class="hljs-keyword">auto</span> e = end(arr);            <span class="hljs-comment">// &#x5168;&#x5C40;&#x51FD;&#x6570;&#x83B7;&#x53D6;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x672B;&#x7AEF;</span>

assert(distance(b, e) == <span class="hljs-number">5</span>);  <span class="hljs-comment">// &#x8FED;&#x4EE3;&#x5668;&#x7684;&#x8DDD;&#x79BB;</span>

<span class="hljs-keyword">auto</span> p = next(b);              <span class="hljs-comment">// &#x83B7;&#x53D6;&#x201C;&#x4E0B;&#x4E00;&#x4E2A;&#x201D;&#x4F4D;&#x7F6E;</span>
assert(distance(b, p) == <span class="hljs-number">1</span>);    <span class="hljs-comment">// &#x8FED;&#x4EE3;&#x5668;&#x7684;&#x8DDD;&#x79BB;</span>
assert(distance(p, b) == <span class="hljs-number">-1</span>);  <span class="hljs-comment">// &#x53CD;&#x5411;&#x8BA1;&#x7B97;&#x8FED;&#x4EE3;&#x5668;&#x7684;&#x8DDD;&#x79BB;</span>

advance(p, <span class="hljs-number">2</span>);                <span class="hljs-comment">// &#x8FED;&#x4EE3;&#x5668;&#x524D;&#x8FDB;&#x4E24;&#x4E2A;&#x4F4D;&#x7F6E;&#xFF0C;&#x6307;&#x5411;&#x5143;&#x7D20;&apos;3&apos;</span>
assert(*p == <span class="hljs-number">3</span>);
assert(p == prev(e, <span class="hljs-number">2</span>));     <span class="hljs-comment">// &#x662F;&#x672B;&#x7AEF;&#x8FED;&#x4EE3;&#x5668;&#x7684;&#x524D;&#x4E24;&#x4E2A;&#x4F4D;&#x7F6E;</span>
</code></pre>
<h4 id="243-&#x6392;&#x5E8F;&#x7B97;&#x6CD5;">24.3 &#x6392;&#x5E8F;&#x7B97;&#x6CD5;</h4>
<p>&#x4E00;&#x4E9B;&#x5E38;&#x89C1;&#x95EE;&#x9898;&#x5BF9;&#x5E94;&#x7684;&#x7B97;&#x6CD5;&#xFF1A;</p>
<ul>
<li><p>&#x8981;&#x6C42;&#x6392;&#x5E8F;&#x540E;&#x4ECD;&#x7136;&#x4FDD;&#x6301;&#x5143;&#x7D20;&#x7684;&#x76F8;&#x5BF9;&#x987A;&#x5E8F;&#xFF0C;&#x5E94;&#x8BE5;&#x7528; stable_sort&#xFF0C;&#x5B83;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#xFF1B;</p>
</li>
<li><p>&#x9009;&#x51FA;&#x524D;&#x51E0;&#x540D;&#xFF08;TopN&#xFF09;&#xFF0C;&#x5E94;&#x8BE5;&#x7528; partial_sort&#xFF1B;</p>
</li>
<li>&#x9009;&#x51FA;&#x524D;&#x51E0;&#x540D;&#xFF0C;&#x4F46;&#x4E0D;&#x8981;&#x6C42;&#x518D;&#x6392;&#x51FA;&#x540D;&#x6B21;&#xFF08;BestN&#xFF09;&#xFF0C;&#x5E94;&#x8BE5;&#x7528; nth_element&#xFF1B;</li>
<li>&#x4E2D;&#x4F4D;&#x6570;&#xFF08;Median&#xFF09;&#x3001;&#x767E;&#x5206;&#x4F4D;&#x6570;&#xFF08;Percentile&#xFF09;&#xFF0C;&#x8FD8;&#x662F;&#x7528; nth_element&#xFF1B;</li>
<li>&#x6309;&#x7167;&#x67D0;&#x79CD;&#x89C4;&#x5219;&#x628A;&#x5143;&#x7D20;&#x5212;&#x5206;&#x6210;&#x4E24;&#x7EC4;&#xFF0C;&#x7528; partition&#xFF1B;</li>
<li>&#x7B2C;&#x4E00;&#x540D;&#x548C;&#x6700;&#x540E;&#x4E00;&#x540D;&#xFF0C;&#x7528; minmax_element&#x3002;</li>
</ul>
<pre><code class="lang-cpp"><span class="hljs-comment">// top3</span>
<span class="hljs-built_in">std</span>::partial_sort(
    begin(v), next(begin(v), <span class="hljs-number">3</span>), end(v));  <span class="hljs-comment">// &#x53D6;&#x524D;3&#x540D;</span>

<span class="hljs-comment">// best3</span>
<span class="hljs-built_in">std</span>::nth_element(
    begin(v), next(begin(v), <span class="hljs-number">3</span>), end(v));  <span class="hljs-comment">// &#x6700;&#x597D;&#x7684;3&#x4E2A;</span>

<span class="hljs-comment">// Median</span>
<span class="hljs-keyword">auto</span> mid_iter =                            <span class="hljs-comment">// &#x4E2D;&#x4F4D;&#x6570;&#x7684;&#x4F4D;&#x7F6E;</span>
    next(begin(v), v.size()/<span class="hljs-number">2</span>);
<span class="hljs-built_in">std</span>::nth_element( begin(v), mid_iter, end(v));<span class="hljs-comment">// &#x6392;&#x5E8F;&#x5F97;&#x5230;&#x4E2D;&#x4F4D;&#x6570;</span>
<span class="hljs-built_in">cout</span> &lt;&lt; <span class="hljs-string">&quot;median is &quot;</span> &lt;&lt; *mid_iter &lt;&lt; <span class="hljs-built_in">endl</span>;

<span class="hljs-comment">// partition</span>
<span class="hljs-keyword">auto</span> pos = <span class="hljs-built_in">std</span>::partition(                <span class="hljs-comment">// &#x627E;&#x51FA;&#x6240;&#x6709;&#x5927;&#x4E8E;9&#x7684;&#x6570;</span>
    begin(v), end(v),
    [](<span class="hljs-keyword">const</span> <span class="hljs-keyword">auto</span>&amp; x)                    <span class="hljs-comment">// &#x5B9A;&#x4E49;&#x4E00;&#x4E2A;lambda&#x8868;&#x8FBE;&#x5F0F;</span>
    {
        <span class="hljs-keyword">return</span> x &gt; <span class="hljs-number">9</span>;
    }
); 
for_each(begin(v), pos, print);         <span class="hljs-comment">// &#x8F93;&#x51FA;&#x5206;&#x7EC4;&#x540E;&#x7684;&#x6570;&#x636E;  </span>

<span class="hljs-comment">// min/max</span>
<span class="hljs-keyword">auto</span> value = <span class="hljs-built_in">std</span>::minmax_element(        <span class="hljs-comment">//&#x627E;&#x51FA;&#x7B2C;&#x4E00;&#x540D;&#x548C;&#x5012;&#x6570;&#x7B2C;&#x4E00;</span>
    cbegin(v), cend(v)
);
</code></pre>
<p>&#x5982;&#x679C;&#x662F; list &#x5BB9;&#x5668;&#xFF0C;&#x5E94;&#x8BE5;&#x8C03;&#x7528;&#x6210;&#x5458;&#x51FD;&#x6570; sort()&#xFF0C;&#x5B83;&#x5BF9;&#x94FE;&#x8868;&#x7ED3;&#x6784;&#x505A;&#x4E86;&#x7279;&#x522B;&#x7684;&#x4F18;&#x5316;&#x3002;&#x6709;&#x5E8F;&#x5BB9;&#x5668; set/map &#x672C;&#x8EAB;&#x5C31;&#x5DF2;&#x7ECF;&#x6392;&#x597D;&#x5E8F;&#x4E86;&#xFF0C;&#x76F4;&#x63A5;&#x5BF9;&#x8FED;&#x4EE3;&#x5668;&#x505A;&#x8FD0;&#x7B97;&#x5C31;&#x53EF;&#x4EE5;&#x5F97;&#x5230;&#x7ED3;&#x679C;&#x3002;</p>
<h4 id="244-&#x67E5;&#x627E;&#x7B97;&#x6CD5;">24.4 &#x67E5;&#x627E;&#x7B97;&#x6CD5;</h4>
<p>&#x7B97;&#x6CD5; binary_search&#xFF0C;&#x987E;&#x540D;&#x601D;&#x4E49;&#xFF0C;&#x5C31;&#x662F;&#x5728;&#x5DF2;&#x7ECF;&#x6392;&#x597D;&#x5E8F;&#x7684;&#x533A;&#x95F4;&#x91CC;&#x6267;&#x884C;&#x4E8C;&#x5206;&#x67E5;&#x627E;&#x3002;&#x4F46;&#x53EA;&#x8FD4;&#x56DE;&#x4E00;&#x4E2A; bool &#x503C;&#xFF0C;&#x544A;&#x77E5;&#x5143;&#x7D20;&#x662F;&#x5426;&#x5B58;&#x5728;&#xFF0C;&#x800C;&#x66F4;&#x591A;&#x7684;&#x65F6;&#x5019;&#x662F;&#x60F3;&#x5B9A;&#x4F4D;&#x5230;&#x90A3;&#x4E2A;&#x5143;&#x7D20;&#xFF0C;&#x6240;&#x4EE5; binary_search &#x51E0;&#x4E4E;&#x6CA1;&#x4EC0;&#x4E48;&#x7528;&#x3002;</p>
<pre><code class="lang-cpp"><span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; v = {<span class="hljs-number">3</span>,<span class="hljs-number">5</span>,<span class="hljs-number">1</span>,<span class="hljs-number">7</span>,<span class="hljs-number">10</span>,<span class="hljs-number">99</span>,<span class="hljs-number">42</span>};  <span class="hljs-comment">// vector&#x5BB9;&#x5668;</span>
<span class="hljs-built_in">std</span>::sort(begin(v), end(v));        <span class="hljs-comment">// &#x5FEB;&#x901F;&#x6392;&#x5E8F;</span>

<span class="hljs-keyword">auto</span> found = binary_search(         <span class="hljs-comment">// &#x4E8C;&#x5206;&#x67E5;&#x627E;&#xFF0C;&#x53EA;&#x80FD;&#x786E;&#x5B9A;&#x5143;&#x7D20;&#x5728;&#x4E0D;&#x5728;</span>
    cbegin(v), cend(v), <span class="hljs-number">7</span>
);
</code></pre>
<p>&#x5728;&#x5DF2;&#x5E8F;&#x5BB9;&#x5668;&#x4E0A;&#x6267;&#x884C;&#x4E8C;&#x5206;&#x67E5;&#x627E;&#xFF0C;&#x8981;&#x7528;&#x5230;&#xFF1A;<strong>lower_bound</strong>&#xFF0C;&#x5B83;&#x8FD4;&#x56DE;&#x7B2C;&#x4E00;&#x4E2A;<strong>&#x201C;&#x5927;&#x4E8E;&#x6216;&#x7B49;&#x4E8E;&#x201D;</strong>&#x503C;&#x7684;&#x4F4D;&#x7F6E;&#xFF1A;</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">decltype</span>(cend(v)) pos;            <span class="hljs-comment">// &#x58F0;&#x660E;&#x4E00;&#x4E2A;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x4F7F;&#x7528;decltype</span>

pos = <span class="hljs-built_in">std</span>::lower_bound(          <span class="hljs-comment">// &#x627E;&#x5230;&#x7B2C;&#x4E00;&#x4E2A;&gt;=7&#x7684;&#x4F4D;&#x7F6E;</span>
    cbegin(v), cend(v), <span class="hljs-number">7</span>
);  
found = (pos != cend(v)) &amp;&amp; (*pos == <span class="hljs-number">7</span>); <span class="hljs-comment">// &#x53EF;&#x80FD;&#x627E;&#x4E0D;&#x5230;&#xFF0C;&#x6240;&#x4EE5;&#x5FC5;&#x987B;&#x8981;&#x5224;&#x65AD;</span>
assert(found);                          <span class="hljs-comment">// 7&#x5728;&#x5BB9;&#x5668;&#x91CC;</span>
</code></pre>
<p>lower_bound &#x7684;&#x8FD4;&#x56DE;&#x503C;&#x662F;&#x4E00;&#x4E2A;&#x8FED;&#x4EE3;&#x5668;&#xFF0C;&#x6240;&#x4EE5;&#x5C31;&#x8981;&#x505A;&#x4E00;&#x70B9;&#x5224;&#x65AD;&#x5DE5;&#x4F5C;&#xFF0C;&#x624D;&#x80FD;&#x77E5;&#x9053;&#x662F;&#x5426;&#x771F;&#x7684;&#x627E;&#x5230;&#x4E86;&#x3002;&#x5224;&#x65AD;&#x7684;&#x6761;&#x4EF6;&#x6709;&#x4E24;&#x4E2A;&#xFF0C;&#x4E00;&#x4E2A;&#x662F;&#x8FED;&#x4EE3;&#x5668;&#x662F;&#x5426;&#x6709;&#x6548;&#xFF0C;&#x53E6;&#x4E00;&#x4E2A;&#x662F;&#x8FED;&#x4EE3;&#x5668;&#x7684;&#x503C;&#x662F;&#x4E0D;&#x662F;&#x8981;&#x627E;&#x7684;&#x503C;&#x3002;</p>
<p> lower_bound &#x7684;&#x67E5;&#x627E;&#x6761;&#x4EF6;&#x662F;&#x201C;&#x5927;&#x4E8E;&#x7B49;&#x4E8E;&#x201D;&#xFF0C;&#x800C;&#x4E0D;&#x662F;&#x201C;&#x7B49;&#x4E8E;&#x201D;&#xFF0C;&#x6240;&#x4EE5;&#x5B83;&#x7684;&#x771F;&#x6B63;&#x542B;&#x4E49;&#x662F;&#x201C;&#x5927;&#x4E8E;&#x7B49;&#x4E8E;&#x503C;&#x7684;&#x7B2C;&#x4E00;&#x4E2A;&#x4F4D;&#x7F6E;&#x201D;&#x3002;&#x76F8;&#x5E94;&#x7684;&#x4E5F;&#x5C31;&#x6709;<strong>&#x201C;&#x5927;&#x4E8E;&#x7B49;&#x4E8E;&#x503C;&#x7684;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x4F4D;&#x7F6E;&#x201D;</strong>&#xFF0C;&#x7B97;&#x6CD5;&#x53EB; <strong>upper_bound</strong>&#xFF0C;&#x8FD4;&#x56DE;&#x7684;&#x662F;&#x7B2C;&#x4E00;&#x4E2A;&#x201C;&#x5927;&#x4E8E;&#x201D;&#x503C;&#x7684;&#x5143;&#x7D20;&#x3002;</p>
<pre><code class="lang-cpp">pos = <span class="hljs-built_in">std</span>::upper_bound(             <span class="hljs-comment">// &#x627E;&#x5230;&#x7B2C;&#x4E00;&#x4E2A;&gt;9&#x7684;&#x4F4D;&#x7F6E;</span>
    cbegin(v), cend(v), <span class="hljs-number">9</span>
);
</code></pre>
<p>&#x4E24;&#x8005;&#x7684;&#x533A;&#x5206;&#x53EF;&#x4EE5;&#x501F;&#x52A9;&#x4E00;&#x4E2A;&#x7B80;&#x5355;&#x7684;&#x4E0D;&#x7B49;&#x5F0F;&#xFF1A;</p>
<pre><code>begin &lt; x &lt;= lower_bound &lt; upper_bound &lt; end
</code></pre><p>&#x6709;&#x5E8F;&#x5BB9;&#x5668; set/map&#xFF0C;&#x5C31;&#x4E0D;&#x9700;&#x8981;&#x8C03;&#x7528;&#x8FD9;&#x4E09;&#x4E2A;&#x7B97;&#x6CD5;&#x4E86;&#xFF0C;&#x5B83;&#x4EEC;&#x6709;&#x7B49;&#x4EF7;&#x7684;&#x6210;&#x5458;&#x51FD;&#x6570;find/lower_bound/upper_bound&#xFF0C;&#x6548;&#x679C;&#x662F;&#x4E00;&#x6837;&#x7684;&#x3002;</p>
<pre><code class="lang-cpp"><span class="hljs-built_in">multiset</span>&lt;<span class="hljs-keyword">int</span>&gt; s = {<span class="hljs-number">3</span>,<span class="hljs-number">5</span>,<span class="hljs-number">1</span>,<span class="hljs-number">7</span>,<span class="hljs-number">7</span>,<span class="hljs-number">7</span>,<span class="hljs-number">10</span>,<span class="hljs-number">99</span>,<span class="hljs-number">42</span>};  <span class="hljs-comment">// multiset&#xFF0C;&#x5141;&#x8BB8;&#x91CD;&#x590D;</span>

<span class="hljs-keyword">auto</span> pos = s.find(<span class="hljs-number">7</span>);                      <span class="hljs-comment">// &#x4E8C;&#x5206;&#x67E5;&#x627E;&#xFF0C;&#x8FD4;&#x56DE;&#x8FED;&#x4EE3;&#x5668;</span>
assert(pos != s.end());                   <span class="hljs-comment">// &#x4E0E;end()&#x6BD4;&#x8F83;&#x624D;&#x80FD;&#x77E5;&#x9053;&#x662F;&#x5426;&#x627E;&#x5230;</span>

<span class="hljs-keyword">auto</span> lower_pos = s.lower_bound(<span class="hljs-number">7</span>);       <span class="hljs-comment">// &#x83B7;&#x53D6;&#x533A;&#x95F4;&#x7684;&#x5DE6;&#x7AEF;&#x70B9;</span>
<span class="hljs-keyword">auto</span> upper_pos = s.upper_bound(<span class="hljs-number">7</span>);       <span class="hljs-comment">// &#x83B7;&#x53D6;&#x533A;&#x95F4;&#x7684;&#x53F3;&#x7AEF;&#x70B9;</span>

for_each(                                <span class="hljs-comment">// for_each&#x7B97;&#x6CD5;</span>
    lower_pos, upper_pos, print          <span class="hljs-comment">// &#x8F93;&#x51FA;7,7,7</span>
);
</code></pre>

                                
                                </section>
                            
    </div>
    <div class="search-results">
        <div class="has-results">
            
            <h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
            <ul class="search-results-list"></ul>
            
        </div>
        <div class="no-results">
            
            <h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
            
        </div>
    </div>
</div>

                        </div>
                    </div>
                
            </div>

            
                
                <a href="../五、C++内存管理/" class="navigation navigation-prev " aria-label="Previous page: 五、C++内存管理">
                    <i class="fa fa-angle-left"></i>
                </a>
                
                
                <a href="../七、C++新特性/" class="navigation navigation-next " aria-label="Next page: 七、C++新特性">
                    <i class="fa fa-angle-right"></i>
                </a>
                
            
        
    </div>

    <script>
        var gitbook = gitbook || [];
        gitbook.push(function() {
            gitbook.page.hasChanged({"page":{"title":"六、C++STL C库函数","level":"1.7","depth":1,"next":{"title":"七、C++新特性","level":"1.8","depth":1,"path":"七、C++新特性/README.md","ref":"./七、C++新特性/README.md","articles":[]},"previous":{"title":"五、C++内存管理","level":"1.6","depth":1,"path":"五、C++内存管理/README.md","ref":"./五、C++内存管理/README.md","articles":[]},"dir":"ltr"},"config":{"plugins":["-lunr","-sharing","-search","-favicon","-code","expandable-chapters","intopic-toc","back-to-top-button","search-pro","splitter","pageview-count"],"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"pluginsConfig":{"intopic-toc":{"isCollapsed":false,"isScrollspyActive":true,"label":{"de":"In diesem Artikel","en":"In this article"},"maxDepth":2,"mode":"nested","selector":".markdown-section h1, .markdown-section h2, .markdown-section h3, .markdown-section h4, .markdown-section h5, .markdown-section h6","visible":true},"splitter":{},"search-pro":{},"code":{"copyButtons":true},"fontsettings":{"theme":"white","family":"sans","size":2},"highlight":{},"back-to-top-button":{},"pageview-count":{},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false},"expandable-chapters":{}},"theme":"default","author":"songzhuozhu","lang":"zh-cn","pdf":{"pageNumbers":true,"fontSize":12,"fontFamily":"Arial","paperSize":"a4","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56}},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"variables":{"themeLou":{"nav":[{"target":"_blank","url":"https://github.com/zhuozhudd","name":"Github"}]}},"title":"CppInterview","gitbook":"*","description":"秋招总结"},"file":{"path":"六、C++STL C库函数/README.md","mtime":"2021-11-15T02:40:52.793Z","type":"markdown"},"gitbook":{"version":"3.2.3","time":"2021-11-15T03:17:42.817Z"},"basePath":"..","book":{"language":""}});
        });
    </script>
</div>

        
    <script src="../gitbook/gitbook.js"></script>
    <script src="../gitbook/theme.js"></script>
    
        
        <script src="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-intopic-toc/anchor.min.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-intopic-toc/gumshoe.polyfills.min.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-intopic-toc/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-back-to-top-button/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/jquery.mark.min.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/search.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-splitter/splitter.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-pageview-count/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
        
    

    </body>
</html>

